Content deleted Content added
→State complexity tradeoffs: Wrote about the 2DFA vs 2NFA problem |
|||
Line 69:
| doi = 10.1007/11549345_47
}}</ref> determined that transforming an <math>n</math>-state 2DFA to an equivalent DFA requires <math>n(n^n-(n-1)^n)</math> states in the worst case. If an <math>n</math>-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>.
{{unsolved|computer science|Does every n-state 2NFA have an equivalent poly(n)-state 2DFA?}}
It is an open problem whether every 2NFA can be converted to a 2DFA
with only a polynomial increase in the number of states.
The problem was raised by Sakoda and [[Michael Sipser|Sipser]]<ref>{{cite conference
| title = Nondeterminism and the Size of Two Way Finite Automata
| first1 = William J.
| last1 = Sakoda
| first2 = Michael
| last2 = Sipser
| year = 1978
| conference = STOC 1978
| publisher = ACM
| ___location =
| pages = 275-286
| doi = 10.1145/800133.804357
}}</ref>,
who compared it to the [[P vs. NP]] problem
in the [[computational complexity theory]].
Berman and Lingas<ref>{{cite conference
| title = On the complexity of regular languages in terms of finite automata
| first1 = Piotr
| last1 = Berman
| first2 = Andrzej
| last2 = Lingas
| year = 1977
| volume = Report 304
| publisher = Polish Academy of Sciences
}}</ref> discovered a formal relation between this problem
and the [[L (complexity)|L]] vs. [[NL (complexity)|NL]] open problem,
see [[Kapoutsis, Christos|Kapoutsis]]<ref>{{cite journal
| last = Kapoutsis
| first = Christos A.
| date = 2014
| title = Two-Way Automata Versus Logarithmic Space
| journal = Theory of Computing Systems
| volume = 55
| issue = 2
| pages = 421-447
| doi = 10.1007/s00224-013-9465-0
}}</ref> for a precise relation.
==Two-way quantum finite automaton==
| |||