State complexity: Difference between revisions

Revision as of 20:30, 22 March 2017

Revision as of 15:30, 23 March 2017

Line 171:

* 2DFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />

* 2DFA2NFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />

===Complementation===

Line 225:

Surveys of state complexity

were written by Holzer and Kutrib<ref name="HolzerKutrib2009">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Nondeterministic finite automata — recent results on the descriptional and computational complexity|journal=International Journal of Foundations of Computer Science|volume=20|issue=4|year=2009|pages=563–580|issn=0129-0541|doi=10.1142/S0129054109006747}}</ref><ref name="HolzerKutrib2011">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Descriptional and computational complexity of finite automata—A survey|journal=Information and Computation|volume=209|issue=3|year=2011|pages=456–470|issn=08905401|doi=10.1016/j.ic.2010.11.013}}</ref>

and by Gao et al.<ref>{{cite arxiv| eprint=1509.03254v1| last1=Gao| first1=Yuan| title=A Survey on Operational State Complexity| last2=Moreira| first2=Nelma| last3=Reis| first3=Rogério| last4=Yu| first4=Sheng| class=cs.FL| year=2015}}</ref>

New research on state complexity