Content deleted Content added
removed link(s) to deleted page(s) per WP:RED |
m Open access bot: hdl, doi added to citation with #oabot. |
||
Line 142:
* 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">{{Cite book|last1=Jirásek|first1=Jozef|title=Operations on Unambiguous Finite Automata|last2=Jirásková|first2=Galina|last3=Šebej|first3=Juraj|volume=9840|year=2016|pages=243–255|issn=0302-9743|doi=10.1007/978-3-662-53132-7_20|series=Lecture Notes in Computer Science|isbn=978-3-662-53131-0}}</ref>
* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015">{{Cite book|last1=Jirásek|first1=Jozef Štefan|title=Computer Science -- Theory and Applications|last2=Jirásková|first2=Galina|last3=Szabari|first3=Alexander|volume=9139|year=2015|pages=231–261|issn=0302-9743|doi=10.1007/978-3-319-20297-6_16|series=Lecture Notes in Computer Science|isbn=978-3-319-20296-9}}</ref>
* 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|doi-access=free}}</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|issue=1–4|year=2011|pages=231–239|doi=10.3233/FI-2011-540}}</ref>
Line 205:
* 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">{{Cite book|last1=Kunc|first1=Michal|title=Developments in Language Theory|last2=Okhotin|first2=Alexander|volume=6795|year=2011|pages=324–336|issn=0302-9743|doi=10.1007/978-3-642-22321-1_28|series=Lecture Notes in Computer Science|isbn=978-3-642-22320-4|citeseerx=10.1.1.616.8835}}</ref>
* 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|hdl=2434/35121|hdl-access=free}}</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=1–3|year=2003|pages=189–203|issn=0304-3975|doi=10.1016/S0304-3975(02)00403-6}}</ref>
* 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" />
| |||