Hot answers tagged

12

The bounds... We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper. ...cannot be substantially improved There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof ...


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


7

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are reachable from the start state Helpful subroutine Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate ...


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


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


5

Your problem is NP-hard, by reduction from 3SAT. Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as follows. The $n$-bit input to the NFA is treated as an assignment to $x_1,\dots,x_n$. The NFA first nondeterministically selects one of the $m$ clauses. Then, it ...


5

This model is one of the standard models in automata theory and it has been examined by some researchers. The references given in the first comment are very good starting points. When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my ...


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

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this. Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata ...


3

A model that seems somewhat relevant is capacitated automata: http://www.cs.huji.ac.il/~ornak/publications/fsttcs14b.pdf


3

I think the easiest way of enforcing tree shape is the set of conditions $q_0$ is not in the image of $\delta$, $\delta$ is injective, and $M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable. Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.


3

Lemma 1. $H_{\textsf{2nfa}}$ is decidable. Proof. Decide it as follows. Given as input a two-way non-deterministic finite automaton $M_{\textsf{2nfa}}$: Convert $M_{\textsf{2nfa}}$ into a two-way alternating finite automaton $M_{\textsf{2wafa}}$ such that the language of $M_{\textsf{2wafa}}$ is $$L(M_{\textsf{2wafa}}) = \{x \in \Sigma^* : \text{ all ...


2

I guess the main reason why you could not find anything about this is that it is rarely needed (and can be reduced to the better-known boolean operations, as you noted). Checking language equivalence of two automata is close, but there you don't necessarily want to compute the symmetric difference exactly, just check whether it is empty. One way of ...


2

Yes, see for example here: Johanna Högberg, Andreas Maletti, Jonathan May, Backward and forward bisimulation minimization of tree automata, Theoretical Computer Science 410(37), 2009, pp. 3539-3552, https://doi.org/10.1016/j.tcs.2009.03.022


2

Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots $ and $v_1,\dots,v_n,\dots $ such that: For each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters; $S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$. ...


1

Another idea, inspired by the pump lemma, would be to just say that there exists a maximum size N on words in the language, with N < |Q|. if there was a cycle, then you could repeat the cycle indefinitely and have a word of arbitrary size ; if you can't, then there's no cycle and your automata is a tree.


1

The easiest way I can think of is to define the constraint in terms of some ordering on the states. For instance: say a $\delta$ is only valid if it respects some total ordering $<$ on $Q$, i.e. only relates elements $p, q \in Q$ for which $p < q$. As the comments point out, that does not suffice: all DAGs meet this criterion, not just trees. So ...


1

Such a constraint cannot be expressed within (what is normally considered to be) a transition function for a DFA or NFA, where transitions are specified in terms of triples $(\operatorname{from-state},\operatorname{input-symbol},\operatorname{to-state})$. Hence they are 'local' to the 'from' state, carrying no information about the path from prior states. ...


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