<p>The recent survey <a href="https://arxiv.org/pdf/1208.2755" rel="nofollow noreferrer">Two-Way Finite Automata: Old and Recent Results</a> by Pighizzini states in the introduction:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p><strong>EDIT (2017/09/18):</strong> Concerning upper bounds, the <a href="http://hdl.handle.net/1721.1/37891" rel="nofollow noreferrer" title="PhD thesis">PhD thesis</a> 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:</p>

<blockquote>
  <p>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.
  [...]</p>
  
  <p>² 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$.</p>
</blockquote>

<p><strong>References:</strong></p>

<p>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 &amp; JAC 2012, pp.3-20.</p>

<p>Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.</p>

CC BY-SA 3.0
2017-09-14T14:21:55.917Z
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, http://hdl.handle.net/1721.1/37891 and his paper at MFCS 2005 https://doi.org/10.1007/11549345_47 or http://www.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.
András Salamon
CC BY-SA 3.0
2017-09-14T19:05:25.413Z
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).
Demi
CC BY-SA 3.0
2017-09-14T21:27:24.217Z
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.
Hermann Gruber
CC BY-SA 3.0
2017-09-13T21:23:43.180Z
2017-09-18T21:38:08.593Z
2017-09-18T21:38:08.593Z
Hermann Gruber
<p>Suppose that one has an NFA (from, say, a regular expression).  What is the state complexity of turning it into a 2DFA?</p>

CC BY-SA 3.0
2017-09-11T06:32:25.477Z
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."
D.W.
CC BY-SA 3.0
2017-09-11T06:33:13.140Z
Possibly relevant: https://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton#Sweeping_automata, https://en.wikipedia.org/wiki/State_complexity#Transformation_between_models.  The citations there might be a good place to start a literature search.
D.W.
<fl.formal-languages><space-bounded><dfa><logspace><nfa>
NFA to 2DFA: what are the upper and lower bounds?
Demi
# NFA to 2DFA: what are the upper and lower bounds?

(Asked by: username_0 on 2017-09-11)

Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?

**Tags:** fl.formal-languages, space-bounded, dfa, logspace, nfa

> **Comments:**
> **username_1**: 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."  
> **username_1**: Possibly relevant: https://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton#Sweeping_automata, https://en.wikipedia.org/wiki/State_complexity#Transformation_between_models.  The citations there might be a good place to start a literature search.  

---

## 1 answers

### Answer by username_2 on 2017-09-13. Score: 6

The recent survey [Two-Way Finite Automata: Old and Recent Results](https://arxiv.org/pdf/1208.2755) 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](http://hdl.handle.net/1721.1/37891 "PhD thesis") of Christos Kapoutsis provides a valuable source (thanks goes to username_3 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.

> **Comments:**
> **username_3**: 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, http://hdl.handle.net/1721.1/37891 and his paper at MFCS 2005 https://doi.org/10.1007/11549345_47 or http://www.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.  
> **username_0**: 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).  
> **username_2**: 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.  

---

