Revision as of 09:38, 29 March 2017 edit Hosmich (talk \| contribs) 459 edits m NFA intersection is mn ← Previous edit		Revision as of 08:08, 27 August 2017 edit undo Rjwilmsi (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 933,673 edits m →Reversal: Journal cites, Added 1 doi to a journal cite using AWB (12158) Next edit →
Line 187: ===Reversal=== * DFA: <math>2^n</math> states, see Mirkin,<ref name="Mirkin1966">{{cite journal\|last1=Mirkin\|first1=Boris G.\|title=On dual automata\|journal=Cybernetics\|volume=2\|year=1966\|pages=6–9\|doi=10.1007/bf01072247}}</ref> Leiss,<ref name="Leiss1985">{{cite journal\|last1=Leiss\|first1=Ernst\|title=Succinct representation of regular languages by boolean automata II\|journal=Theoretical Computer Science\|volume=38\|year=1985\|pages=133–136\|issn=0304-3975\|doi=10.1016/0304-3975(85)90215-4}}</ref> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" /> * NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" /> * UFA: <math>n</math> states.

State complexity: Difference between revisions