Content deleted Content added
→The 2DFA vs. 2NFA problem and logarithmic space: html math formatting doesn't work inside the unsolved template |
Citation bot (talk | contribs) m Alter: title, template type, issue. Add: isbn, series, format, url, citeseerx, chapter. Formatted dashes. You can use this bot yourself. Report bugs here. | User-activated. |
||
Line 48:
* NFA to UFA: <math>2^n-1</math> states, see Leung.<ref name="Leung2005" /> There was an earlier smaller lower bound by Schmidt.<ref name="Schmidt1978" />
* SVFA to DFA: <math>\Theta(3^{n/3})</math> states, see Jirásková and [[Giovanni Pighizzini|Pighizzini]]<ref name="JiráskováPighizzini2011">{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=0890-5401|doi=10.1016/j.ic.2010.11.017}}</ref>
* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{
* 2DFA to NFA: <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>, see Kapoutsis.<ref name="Kapoutsis2005" /> Earlier construction by [[Jean-Camille Birget|Birget]] <ref name="Birget1993a">{{cite journal|last1=Birget|first1=Jean-Camille|title=State-complexity of finite-state devices, state compressibility and incompressibility|journal=Mathematical Systems Theory|volume=26|issue=3|year=1993|pages=237–269|issn=0025-5661|doi=10.1007/BF01371727}}</ref> used more states.
* 2NFA to NFA: <math>\binom{2n}{n+1}</math>, see Kapoutsis.<ref name="Kapoutsis2005" />
** 2NFA to NFA accepting the complement: <math>O(4^n)</math> states, see [[Moshe Vardi|Vardi]].<ref name="Vardi1989">{{cite journal|last1=Vardi|first1=Moshe Y.|title=A note on the reduction of two-way automata to one-way automata|journal=Information Processing Letters|volume=30|issue=5|year=1989|pages=261–264|issn=0020-0190|doi=10.1016/0020-0190(89)90205-6|citeseerx=10.1.1.60.464}}</ref>
* AFA to DFA: <math>2^{2^n}</math> states, see [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243}}</ref>
* AFA to NFA: <math>2^n</math> states, see Fellah, Jürgensen and Yu.<ref name="FellahJürgensen1990">{{cite journal|last1=Fellah|first1=A.|last2=Jürgensen|first2=H.|last3=Yu|first3=S.|title=Constructions for alternating finite automata∗|journal=International Journal of Computer Mathematics|volume=35|issue=1–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}</ref>
* 2AFA to DFA: <math>2^{n2^n}</math>, see [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>
* 2AFA to NFA: <math>2^{\Theta(n \log n)}</math>, see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{
===The 2DFA vs. 2NFA problem and logarithmic space===
Line 128:
<ref name="YuZhuang1994">{{cite journal|last1=Yu|first1=Sheng|last2=Zhuang|first2=Qingyu|last3=Salomaa|first3=Kai|title=The state complexities of some basic operations on regular languages|journal=Theoretical Computer Science|volume=125|issue=2|year=1994|pages=315–328|issn=0304-3975|doi=10.1016/0304-3975(92)00011-F}}</ref>
[[Markus Holzer|Holzer]] and [[Martin Kutrib|Kutrib]]
<ref name="HolzerKutrib2003">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Nondeterministic descriptional complexity of regular languages|journal=International Journal of Foundations of Computer Science|volume=14|issue=6|year=2003|pages=1087–1102|issn=0129-0541|doi=10.1142/S0129054103002199|url=http://geb.uni-giessen.de/geb/volltexte/2003/1194/|format=Submitted manuscript}}</ref>
pioneered the state complexity of operations on NFA.
The known results for basic operations are listed below.
Line 140:
* DFA: <math>mn</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: between <math>mn+m+n</math> and <math>O(n 2^{0.79m})</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016">{{
* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015">{{
* 2DFA: between <math>m+n</math> and <math>4m+n+4</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State complexity of operations on two-way finite automata over a unary alphabet|journal=Theoretical Computer Science|volume=449|year=2012|pages=106–118|issn=0304-3975|doi=10.1016/j.tcs.2012.04.010}}</ref>
* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata |journal=Fundamenta Informaticae|volume=110|year=2011|pages=231–239|doi=10.3233/FI-2011-540|doi-broken-date=2017-03-22}}</ref>
Line 175:
* UFA: <math>\frac{3}{4} 2^{m+n}-1</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />
* SVFA: <math>\Theta(3^{n/3}2^m)</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />
* 2DFA: at least <math>\frac{2^{\Omega(n)}}{\log m}</math> and at most <math>2m^{m+1}\cdot 2^{n^{n+1}}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008">{{
===Kleene star===
Line 204:
* NFA to DFA: <math>g(n)+O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2DFA to DFA: <math>g(n)+O(n)</math> states, see Chrobak<ref name="Chrobak1986" /> and Kunc and Okhotin.<ref name="KuncOkhotin2011b">{{
* 2NFA to DFA: <math>O(g(n))</math> states, see Mereghetti and [[Giovanni Pighizzini|Pighizzini]].<ref name="MereghettiPighizzini2001">{{cite journal|last1=Mereghetti|first1=Carlo|last2=Pighizzini|first2=Giovanni|title=Optimal Simulations between Unary Automata|journal=SIAM Journal on Computing|volume=30|issue=6|year=2001|pages=1976–1992|issn=0097-5397|doi=10.1137/S009753979935431X}}</ref> and [[Viliam Geffert|Geffert]], Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Converting two-way nondeterministic unary automata into simpler automata|journal=Theoretical Computer Science|volume=295|issue=
* NFA to 2DFA: at most <math>O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2NFA to 2DFA: at most <math>n^{O(\log n)}</math> states, proved by implementing the method of [[Savitch's theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003" />
| |||