Content deleted Content added
→Complementation: mention earlier raskin result |
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 143:
* 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: at least <math>\min(n,m)^{\Omega(\log(\min(n,m)))}</math>;<ref name="GoosKieferYuan2022" /> between <math>mn+m+n</math> and <math>m + nm 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>
Line 166:
* DFA: <math>n</math> states, by exchanging accepting and rejecting states.
* NFA: <math>2^n</math> states, see Birget.<ref name="Birget1993b">{{cite journal|last1=Birget|first1=Jean-Camille|title=Partial orders on words, minimal elements of regular languages, and state complexity|journal=Theoretical Computer Science|volume=119|issue=2|year=1993|pages=267–291|issn=0304-3975|doi=10.1016/0304-3975(93)90160-U}}</ref> or Jirásková<ref>{{Cite journal |last=Jirásková |first=Galina |date=2005 |title=State complexity of some operations on binary regular languages |url=https://linkinghub.elsevier.com/retrieve/pii/S0304397504006577 |journal=Theoretical Computer Science |language=en |volume=330 |issue=2 |pages=287–298 |doi=10.1016/j.tcs.2004.04.011}}, Theorem 5</ref>
* UFA: at least <math>n^{\tilde{\Omega}(\log n)}</math> states, see Göös, Kiefer and Yuan,<ref name="GoosKieferYuan2022">{{cite arXiv |last1=Göös |first1=Mika |last2=Kiefer |first2=Stefan |last3=Yuan |first3=Weiqiang |title=Lower Bounds for Unambiguous Automata via Communication Complexity |date=12 February 2022 |class=cs.FL |eprint=2109.09155}}</ref> (this follows an earlier bound by Raskin<ref>{{Cite journal |last=Raskin |first=Mikhail |date=2018 |title=A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.
* 2DFA: at least <math>n</math> and at most <math>4n</math> states, see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Complementing two-way finite automata|journal=Information and Computation|volume=205|issue=8|year=2007|pages=1173–1187|issn=0890-5401|doi=10.1016/j.ic.2007.01.008|doi-access=free}}</ref>
Line 232:
* DFA: <math>n</math> states.
* NFA: <math>g(n)+O(n^2)</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>n^{(\log \log \log n)^{\Theta(1)}}</math> states, see Raskin,<ref name="Raskin2018">{{cite conference |last1=Raskin|first1=Michael|title=A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton|pages=138:1–138:11|book-title=Proc. ICALP 2018|year=2018|doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }}</ref> and at most <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math> states, see Okhotin.<ref name="Okhotin2012" />
* 2DFA: at least <math>n</math> and at most <math>2n+3</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: at least <math>n</math> and at most <math>O(n^8)</math> states. The upper bound is by implementing the method of the [[Immerman–Szelepcsényi theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007"/>
Line 270:
{{reflist}}
[[Category:Finite-state
| |||