Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
3
votes
2answers
52 views
Simplification of weighted NFA
What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
-2
votes
0answers
18 views
If the reversal of the complement of a language is CFL does the complement of the reversal also CFL? [migrated]
Let $L$ be a language such that $Reversal(Complement(L))\in{CFL}$, does $Complement(Reversal(L))\in{CFL}$
0
votes
0answers
7 views
Is there some way how to create NFA based on DFA? [migrated]
Of course, converting Non-Deterministic finite automaton to Deterministic is not a problem. But what about other direction?
My motivation is the notion of minimization regular expression using ...
1
vote
1answer
52 views
Are Reversal-bounded Multicounter Machines closed under reversal?
This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines.
Reversal-bounded multicounter machines are described at length in his ...
10
votes
1answer
219 views
Is there a book/survey-paper outlining language class hierarchies, closure properties, etc
I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack ...
-4
votes
0answers
26 views
write implementation code for this transition in any program language [closed]
where qo,q1,q2, are three states
from qo when accept a goes to q1
from qo when accept b goes to q0
q1 when accept a goes to q2
q1 when accept b goes to qo
q2 when accept a goes to q2
q2 when accept b ...
-1
votes
0answers
75 views
Study groups for theoretical computer science aspirants [migrated]
Recently I decided to go deeper on the subjects like automata, algorithms and graph theory etc. but while reading these either I feel bored or confused hence instead of passive learning I want ...
-2
votes
0answers
25 views
construct a TM from a PDA [migrated]
Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.
My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add ...
4
votes
3answers
167 views
Chomsky hierarchy for tree structures
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.
Is there a similar hierarchy for ...
2
votes
1answer
80 views
Number of accepting path of a non deterministic automaton
I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.
I have got a ...
0
votes
0answers
88 views
Is there a way to transform a Turing machine into an oblivious turing machine that decides the same langauage?
Suppose you have turing machine M that decides L. Is there a simple way to convert this turing machine into an oblivious turing machine M' that decides the same language? My intuition says yes but i ...
-1
votes
1answer
45 views
Constructing automata with the same traces, but where a CTL-formula is not equally satisfied
Hard to put this question in a short title. As part of a self-exercise, I'm trying to solve 6.15b of Principles of Model Checking by Baier and Katoen. You're supposed to prove that there does not ...
6
votes
1answer
163 views
Complete problems and universal simulator machines
I'm trying to get straight in my mind the relation between complete problems and universal simulator machines. Some notions of computability have universal machines (Turing-computability) and some ...
1
vote
1answer
53 views
Deterministic Buchi + its complement covers LTL?
It is well known that deterministic Buchi automata (DBA) are less expressive than non-deterministic Buchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). ...
3
votes
0answers
264 views
Name this digraph
I am trying to track down the name of this digraph and some references:
You take all members of the transformation semigroup on $n$ elements, $T_{n}$.
For two members $x$ ,$y$ ; if $x$ is in the ...
1
vote
0answers
74 views
What is the relationship between the number of states in Quantum Finite Automata and the number of non-regular languages they can recognize?
It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular ...
6
votes
1answer
116 views
Measurable language which is not $\omega$-regular
Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider
$$
d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)}
$$
to be the metric on ...
6
votes
0answers
100 views
Size complexity of probabilistic two-way automata for a Boolean function
I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
3
votes
2answers
232 views
Finite state transducer that sorts
Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers ...
0
votes
2answers
160 views
Find minimum number of transformations to transform from input to target string
Given that I have an input string, for example: aab
And I am given a target string, for example: bababa
And then I am given a ...
5
votes
0answers
152 views
Multi-language DFA minimisation
I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial ...
-1
votes
0answers
77 views
How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)? [closed]
How do you say "δ:Q×Σ→Q" in English? Describing what "×" and "→" mean would also help.
0
votes
1answer
114 views
How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example)
I am looking for a preferably simple property that is expressible in ECTL* but not in CTL* and not in Büchi, with a citable reference to the proof.
Details of what I've tried:
I've tried a ...
2
votes
2answers
145 views
Alternating automata
In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux) the authors, while defining co-Buchi alternating automata define $\Sigma’= 2^\Sigma$ where $\Sigma$ is the alphabet.
...
3
votes
2answers
200 views
Inductive definition of ECTL*: how are recursive formulas forbidden?
In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
4
votes
1answer
207 views
Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( ...
-6
votes
1answer
106 views
Minimizing edges of an FSM [closed]
There are various well-understood, efficient, and theoretically interesting algorithms to minimize a DFA in terms of states.
Is there research into minimizing based on edges of the FSM?
edit: ...
11
votes
1answer
208 views
The Cost of an Equivalence Query for DFA
Inspired by this question, I am curious about the following:
What is the worst-case complexity of checking whether a given DFA accepts the same
language as a given regular expression?
Is this ...
6
votes
1answer
349 views
What algorithms exist for construction a DFA that recognizes the language described by a given regex?
All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, ...
0
votes
2answers
105 views
iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation
A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
2
votes
2answers
472 views
Why were Finite Automata and Turing Machines created?
It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
114
votes
10answers
35k views
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
11
votes
2answers
268 views
Why is the state of a FSM traditionally denoted $q$?
While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is ...
5
votes
0answers
114 views
A language outside the Boolean closure of stochastic languages
Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages.
I have two ...
0
votes
0answers
66 views
Automatic structures/functions: Is (Z,+) under a unary representation automatic?
The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with ...
9
votes
2answers
193 views
The significance of state complexity in automata and regular languages?
I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
5
votes
1answer
165 views
Non-isomorphic minimal non-deterministic finite automata
Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?
4
votes
1answer
94 views
State transducers for generating permutations
Let a finite alphabet $\Sigma$.
Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the ...
-4
votes
1answer
206 views
Minimal Turing Machine implementation / Von Neumann UC [closed]
I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
0
votes
0answers
68 views
Generalizing a set of positive and negative examples through DFAs [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two ...
4
votes
1answer
105 views
Getting an automaton from set of words in and out of a language [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets ...
0
votes
1answer
128 views
Implicit Non-deterministic Buchi determinization
I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states.
But instead of using acceptance states, I am using final state (as in ...
3
votes
0answers
138 views
Language of stack configurations of a pushdown automaton
Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free ...
6
votes
0answers
168 views
A super-linear time problem in NL
It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 ...
11
votes
2answers
234 views
Unary languages recognized by two-way deterministic counter automata
2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace.
...
9
votes
2answers
296 views
Expressiveness of Büchi vs CTL(*)
What is the relationship between the expressiveness of LTL, Büchi/QPTL, CTL and CTL*?
Can you give some references that cover as many of these temporal logics as possible (especially between linear- ...
10
votes
2answers
435 views
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense ...
5
votes
0answers
146 views
Can multipebble automata decide all deterministic context-sensitive languages?
A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is ...
3
votes
1answer
175 views
Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet
For a given finite alphabet $\Sigma$, my goal is to write an algorithm
that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets
($V_{i}\subseteq\Sigma$), and returns a weighted ...
6
votes
0answers
200 views
Examples of non-CSLs not created through diagonalization
Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
