Hot answers tagged

61

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit. Let $u$ and $v$ be two distinct words with $|u|=|v|=n$. What is the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa? Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{...


48

Here's a very simple decision problem about DFA's. Given a DFA M, does M accept the base-2 representation of at least one prime number? Currently, we don't even know if this problem is recursively solvable. If it is recursively solvable, and we had an algorithm for it, we could resolve the longstanding open problem about whether there are any Fermat ...


44

The Černý conjecture is still open and important. It is about DFAs that have a synchronizing word (a word with the property that two copies of the automaton started in different states always end up in the same state as each other after both processing the word), and asks whether (for $n$-state automata) the length of the shortest such word is always at most ...


23

Title: Intersection non-emptiness for two DFA's Description: Given two DFA's $D_1$ and $D_2$, does there exist a string $x$ such that $D_1$ and $D_2$ both accept $x$? Open Problem: Can we solve intersection non-emptiness for two DFA's in $o(n^2)$ time? If we could solve this problem in $O(n^{\delta})$ time where $\delta$ < 2, then the strong ...


20

I want to point out the another research problem, which concerns the interplay of very basic concepts about DFAs. It is well known that any n-state NFA can be converted into an equivalent DFA having at most $2^n$ states. This is best possible in the worst case, in the sense that there are regular languages of nondeterministic state complexity n (i.e., the ...


14

Short answer. Given a finite family of regular languages $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$, there is a unique minimal deterministic complete multi-automaton recognizing this family. Details. The case $n = 1$ corresponds to the standard construction and the general case is not much different in spirit. Given a language $L$ and a word $u$, ...


13

Minimal cover automata is one of a related stuff. Given a finite language $L$, we can obtain a minimal DFA for $L$. But if we relax requirements of DFA we can find smaller ones. We know that longest word in a finite language $L$ has length $l$. Define DFCA as a DFA which accepts only words in $L$ or possibly words which are longer than $l$. Then this DFCA ...


12

Here's an open problem relating DFA and machine learning theory: are uniformly random (random transitions and accept/reject behavior) DFA learnable in the PAC model? Note: we think arbitrary DFA are not learnable b/c of cryptographic hardness results. For random DFA, we only have SQ lower bounds, which are not as strong.


11

If I had to do this in practice, I would use a SAT solver. The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance. For instance, one way is to have $2k^2$ boolean variables: $z_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$. Then add some ...


10

As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions. The first result concerns the reduction of linear representations of recognizable series (= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an ...


10

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA. Proof. Here's the ...


9

Yes, there are some cases of the DFA non emptiness insersection problem that are inside P. My master's thesis is devoted to this question, but unfortunately it is in French. However, most of the results have appeared here in $[2]$. When the alphabet is unary, then the problem is L-complete when each DFA has at most two final states, and NP-complete ...


8

The other contributor deleted his answer, maybe to let me extend my above comment, so here it is. Let $T$ be a possibly nondeterministic transducer, and $L$ be a regular language. Modify $T$ into a transducer $T'$ that checks that its input is in $L$ (by, e.g., changing the state set into the Cartesian product of the state sets of $T$ and $L$, and ...


8

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.


8

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is $$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$ It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-...


7

How many regular languages are there whose minimal DFA has exactly $n$ states? It seems to me that a closed-form formula should exist, but none is known. Some asymptotic bounds are known: On the number of distinct languages accepted by finite automata with $n$ states. M Domaratzki, D Kisman, J Shallit.


7

Recall that, in the case of finite state automata, the notion of a minimal automaton is usually meant for deterministic automata only; you can define it for non-deterministic ones, but then you lose two important properties: canonicity (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and the ...


7

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the ...


6

Have you tried Brzozowski's algorithm? It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize. The following paper seems relevant: On the performance of automata minimization algorithms, Marco Almeida, Nelma ...


6

The main conferences where automata are among the main topics are ICALP, LICS, STACS, CSL, MFCS, FSTTCS. If you feel your paper is not strong enough for these conferences (which accept about a quarter of the papers that are sent each year), you can send to conferences which are a little less exigeant. The ICALP submission deadline is soon (in a week), ...


6

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.


6

The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words. It can be adapted more easily to finite words. In the powerset construction, we simultaneously keep track of all possible runs of the $n$-state automaton, by moving around $n$ tokens. But we could decide to follow only $k<n$ runs, and do ...


6

The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction: The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs are still unknown. The problem of stating them was raised in 1978 by Sakoda and Sipser [32], with the conjecture that they are not polynomial. In spite of all attempts to ...


5

Here is a DFA-related question I'd posted here before, and it's still open as far as I know: Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$. ...


5

This is a very partial answer, but I have some ideas: Clearly the union of NSAs can be taken without any blowup - just use the nondeterministic union of the initial states. As for determinization, you'll have a double-exponential blowup. Consider the language $L_k=(a+b)^*a(a+b)^k$. That is, the $k$-th before last letter is $a$. You can easily construct an ...


5

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for any non-trivial language with a transition $q_0\to q$. Then no such morphism can exist, because we must have $h(p_0)=q_0$, but also $h(p_0)=q$ because of the ...


5

The algorithm is named RPNI, not RNPI. Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., minimal) DFA for that language. If the generating language is not regular, the automaton may grow unboundedly with the set of inputs. Since the algorithm ...


5

Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly, it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link. https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22


5

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $<n$ states then both of the sequences $\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$ and $\delta_{10^n}^{\circ m}(q_0)$ will reach a cycle ...


5

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states. An exponential lower bound on $f$ can be given as follows. Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...


Only top voted, non community-wiki answers of a minimum length are eligible