10

The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete: Input: Integer $k$ and sets $P, N \subseteq \Sigma^*$ Question: Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ ...


9

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 ...


8

This is coNP-hard even if $B$ is also acyclic. Let $D = \bigvee_{i=1}^m T_i$ be a DNF on variables $x_1, \dots, x_n$. We can easily contruct an NFA $B$ accepting exactly the satisfying assignment of $D$, that is, the words $w \in \{0,1\}^n$ such that the assignment $a$ defined as $a(x_i) = w_i$ satisfies $D$. To do this, you build an automaton $B_i$ with $...


8

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$...


6

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages. Recall that an $\omega$-regular expression is of the form $s_1\cdot t_1^\omega+\ldots+s_k \cdot t_k^\omega$, where all the $s_i$ and $t_i$ are regular expressions. The translation of an NBW $A$ to such an ...


6

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: ...


6

Here is a second, simpler and more general answer that was obtained after discussing with a3nm. Problem We fix a regular language $\mathcal{L}$ and we are interested in the following word problem. At start, we have an empty word and then we receive updates taking one of the following forms: Insert a letter at the beginning of the word Insert a letter at ...


6

Context Let $\mathcal{L}$ be a fixed regular language and let ($\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$ be an automaton recognizing $\mathcal{L}$. I will suppose in this post that we are working in the RAM model with cells of size logarithmic in the maximal size of the window, and that all the operations regarding the automaton are constant time. ...


6

Minimizing deterministic Büchi automata is NP-complete, see Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata. Deciding whether a coBüchi automaton is determinizable by pruning is also NP-complete, see Computing the Width of Non-deterministic Automata.


5

Counter Automata I was a co-author for a paper where we investigated this problem for counter automata. We were able to show that the length of a shortest string accepted by an $n$-state (non-empty) counter automaton is at most $\Theta(n^2)$. See here: https://lmcs.episciences.org/5251 The lower bound can be obtained similar to how you described in your ...


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

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


4

First, a warning: this will involve exponential $(2^{n \log n})$ blowup in the number of states (see here). However, if your application is fine with computing the states of the DFA "on the fly" then you can avoid the exponential blowup -- you will get an algorithm for the normal DFA where the state is represented using $O(n)$ memory. Conversion from 2DFA ...


4

Here is another NP-complete variation of the DFA intersection non-emptiness problem. (1) Given a list of DFA's and a number $n$ (in unary), does there exist a string of length at most $n$ that is accepted by all of the DFA's? Also, here are two NP-complete variations of the DFA non-emptiness problem. (2) Given a 2DFA and a number $n$ (in unary), does ...


3

The following paper: http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup. Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).


3

I am not quite sure what you mean by algebraic. But if you mean by just using the definition in terms of recognizing morphisms in such a manner that the proof would easily generalize to other monoids, then this would not be possible. The reason is that recognizable languages in general are not closed under Kleene star. Or more specifically, in general we ...


3

A nice question! Time to get Garey and Johnson off the shelf once again. Problem [AL2] in the problem list mentions the following: The nonemptiness problem for deterministic 2-way deterministic finite automata (2DFAs) over unary alphabet is NP-complete. Zvi Galil: Hierarchies of complete problems. Acta Informat. 6, 77-88. Another problem that comes to ...


2

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones: Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472;...


2

To simplify, let $D$ be the domain of $T$ and let $R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition $$ N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*. $$ Here is a formal way to justify your idea. Let $(u,v) \in \Sigma^* \times \Sigma^*$. By definition, $(u,v) \in R^{obl}(T)$ if and only if $(u,v)$ can be ...


2

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e. Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate. Note that no requirement, even on ...


2

Finding the shortest synchronizing word for a DFA, if one exists (or more properly testing the existence of a synchronizing word shorter than a parameter $k$) is NP-complete. See my paper: Eppstein, David (1990), "Reset sequences for monotonic automata", SIAM J. Comput. 19 (3): 500–510, doi:10.1137/0219033, Theorem 8.


2

The conjecture does not hold: Let $L$ be the set of prefixes of $(c^*ac^*b)^*$. Then $L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$. Take the word $\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$. For all $k\in\mathbb N$, we can show that $PF_k(\eta)\not\subseteq L'$, as witnessed by $$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\...


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