Revision as of 17:07, 31 May 2022 edit Headbomb (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, Page movers, File movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors 473,387 edits m Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published) Tag: AWB ← Previous edit		Revision as of 17:14, 31 May 2022 edit undo Citation bot (talk \| contribs) Bots 5,867,843 edits Alter: template type, title. Add: chapter, s2cid, eprint, class. Removed parameters. Some additions/deletions were parameter name changes. \| Use this bot. Report bugs. \| Suggested by Headbomb \| #UCB_toolbar Next edit →
Line 65: there exists a <math>p(n)</math>-state 2DFA. The problem was raised by Sakoda and [[Michael Sipser\|Sipser]],<ref>{{cite conference \| ~~title~~chapter = Nondeterminism and the Size of Two Way Finite Automata \| first1 = William J. \| last1 = Sakoda \| first2 = Michael \| last2 = Sipser \| title = Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 \| year = 1978 \| conference = STOC 1978 Line 164 ⟶ 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> * UFA: at least <math>n^{\tilde{\Omega}(\log n)}</math> states, see Göös, Kiefer and Yuan,<ref name="GoosKieferYuan2022">{{cite ~~arxiv~~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 \|~~arxiv~~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://www.sciencedirect.com/science/article/pii/S0020019022000278 \|access-date=29 May 2022 \|ref=IndzhevKiefer22 \|language=en \|issn=0020-0190}}</ref> * 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}}</ref>

State complexity: Difference between revisions