Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What research have you done? What have you come up with so far? Have you tried picking a standard example that requires an exponentially large DFA, to see how large a 2DFA it needs? As the faq states, "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, not on shirking." $\endgroup$– D.W.Sep 11, 2017 at 6:32
-
3$\begingroup$ Possibly relevant: en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/…. The citations there might be a good place to start a literature search. $\endgroup$– D.W.Sep 11, 2017 at 6:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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 solve it, this problem is still open.
As explained in section 6 of that survey, the question relates to the L vs. NL problem, so it may be not surprising that the problem remains unresolved. Concerning lower bounds, section 5 states the following:
The question 1NFAs versus 2DFAs has been solved in the unary case in [4] by showing that the tight cost is polynomial, more precisely Θ(n²). This gives also the best known lower bound for the general case.
EDIT (2017/09/18): Concerning upper bounds, the PhD thesis of Christos Kapoutsis provides a valuable source (thanks goes to András Salamon for his valuable comment below). Section 2 of the PhD thesis mentions the following:
Second, it is even conjectured that this alleged exponential difference in size between 1NFAs and 2DFAs covers the entire gap from n to $2^n - 1$ which is known to exist between 1NFAs and 1DFAs [35]² In other words, according to this conjecture, a 2DFA trying to simulate a 1NFA may as well drop its bidirectionality, since it is going to be totally useless: its optimal strategy is going to be the well-known brute-force one-way deterministic simulation [47]. So, once more we have an instance of the claim that the obvious, highly inefficient solution is also the optimal one. [...]
² As with 2DFAS (cf. Footnote 1 on page 8), a 1DFA is allowed to reject by just hanging anywhere along its input. Without this freedom, the gap would actually be from $n$ to $2^n$.
References:
Pighizzini, Giovanni: Two-Way Finite Automata: Old and Recent Results. In: E. Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, pp.3-20.
Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.
answered Sep 13, 2017 at 21:23
-
1$\begingroup$ This problem of the best and worst state complexity trade-offs when simulating automata by other automata was addressed in the 2006 PhD thesis of Christos Kapoutsis, hdl.handle.net/1721.1/37891 and his paper at MFCS 2005 doi.org/10.1007/11549345_47 or andrew.cmu.edu/user/cak/reads/2005-MFCS/main.pdf for the preprint version; see Figure 1 for all the known optimal trade-offs. As the answer points out, this particular question is still open. $\endgroup$ Sep 14, 2017 at 14:21
-
2$\begingroup$ What is the best known algorithm? This is meant for practical application – I know that the upper bound is unknown, but I am looking for the best known practical algorithm (in other words). $\endgroup$– DemiSep 14, 2017 at 19:05
-
1$\begingroup$ I would try and look for algorithms converting a 1NFA to a (minimal) 1DFA, since a 1DFA can be interpreted as a special 2DFA whose head moves from left to right only. In addition, maybe you can exploit the fact that a 1DFA accepting the reversal of the given language also makes a valid 2DFA (or at least it can be turned into a 2DFA by adding few additional states). In the best case, a minimal 1DFA accepting the reversal of an n-state 1DFA has only log n states. Brzozowski's algorithm might be useful in this scenario. $\endgroup$ Sep 14, 2017 at 21:27