Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
→Complementation: add other more modern ref |
||
Line 165:
* 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> and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, see Indzhev and Kiefer.<ref>{{cite journal |last1=Indzhev |first1=Emil |last2=Kiefer |first2=Stefan |title=On complementing unambiguous automata and graphs with many cliques and cocliques |journal=Information Processing Letters |date=1 August 2022 |volume=177 |page=106270 |doi=10.1016/j.ipl.2022.106270 |s2cid=234741832 |url=https://ora.ox.ac.uk/objects/uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54/files/rrj4305198 |access-date=29 May 2022 |ref=IndzhevKiefer22 |language=en |issn=0020-0190|doi-access=free |arxiv=2105.07470 }}</ref>
* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.
| |||