State complexity: Difference between revisions

Revision as of 20:19, 22 March 2017

Revision as of 20:30, 22 March 2017

Line 52:

* SVFA to DFA: <math>\Theta(3^{n/3})</math> states, see Jirásková and [[Giovanni Pighizzini|Pighizzini]]<ref name="JiráskováPighizzini2011">{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=08905401|doi=10.1016/j.ic.2010.11.017}}</ref>

* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{cite journal|last1=Kapoutsis|first1=Christos|title=MathematicalRemoving FoundationsBidirectionality offrom Nondeterministic Finite Automata|series=Lecture Notes in Computer Science 2005|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47|chapter=Removing Bidirectionality from Nondeterministic Finite Automata|series=Lecture Notes in Computer Science|isbn=978-3-540-28702-5}}</ref> Earlier construction by [[John Cedric Shepherdson|Shepherdson]]<ref name="Shepherdson1959">{{cite journal|last1=Shepherdson|first1=J. C.|title=The Reduction of Two-Way Automata to One-Way Automata|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=198–200|issn=0018-8646|doi=10.1147/rd.32.0198}}</ref> used more states, and an earlier lower bound by Moore<ref name="Moore1971">{{cite journal|last1=Moore|first1=F.R.|title=On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata|journal=IEEE Transactions on Computers|volume=C-20|issue=10|year=1971|pages=1211–1214|issn=0018-9340|doi=10.1109/T-C.1971.223108}}</ref> was smaller.

* 2DFA to NFA: <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>, see Kapoutsis.<ref name="Kapoutsis2005" /> Earlier construction by [[Jean-Camille Birget|Birget]] <ref name="Birget1993a">{{cite journal|last1=Birget|first1=Jean-Camille|title=State-complexity of finite-state devices, state compressibility and incompressibility|journal=Mathematical Systems Theory|volume=26|issue=3|year=1993|pages=237–269|issn=0025-5661|doi=10.1007/BF01371727}}</ref> used more states.

Line 65:

* 2AFA to DFA: <math>2^{n2^n}</math>, see [[Richard Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>

* 2AFA to NFA: <math>2^{\Theta(n \log n)}</math>, see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{cite journal|last1=Geffert|first1=Viliam|title=MathematicalTransforming FoundationsTwo-Way ofAlternating ComputerFinite ScienceAutomata 2014to One-Way Nondeterministic Automata|last2=Okhotin|first2=Alexander|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25|chapter=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}</ref>

===The 2DFA vs. 2NFA problem and logarithmic space===

{{unsolved|computer science|Does every n-state 2NFA have an equivalent poly(n)-state 2DFA?}}

Line 139:

<ref name="YuZhuang1994">{{cite journal|last1=Yu|first1=Sheng|last2=Zhuang|first2=Qingyu|last3=Salomaa|first3=Kai|title=The state complexities of some basic operations on regular languages|journal=Theoretical Computer Science|volume=125|issue=2|year=1994|pages=315–328|issn=03043975|doi=10.1016/0304-3975(92)00011-F}}</ref>

[[Markus Holzer|Holzer]] and [[Martin Kutrib|Kutrib]]

<ref name="HolzerKutrib2003">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=NONDETERMINISTICNondeterministic DESCRIPTIONALdescriptional COMPLEXITYcomplexity OFof REGULARregular LANGUAGESlanguages|journal=International Journal of Foundations of Computer Science|volume=14|issue=6|year=2003|pages=1087–1102|issn=0129-0541|doi=10.1142/S0129054103002199}}</ref>

pioneered the state complexity of operations on NFA.

The known results for basic operations are listed below.

Line 153:

* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />

* UFA: between <math>mn+m+n</math> and <math>O(n 2^{0.79m})</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016">{{cite journal|last1=Jirásek|first1=Jozef|title=DevelopmentsOperations inon LanguageUnambiguous Finite TheoryAutomata|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|chapter=Operations on Unambiguous Finite Automata|series=Lecture Notes in Computer Science|isbn=978-3-662-53131-0}}</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=03043975|doi=10.1016/j.tcs.2012.04.010}}</ref>

Line 196:

* UFA: <math>\frac{3}{4} 2^{m+n}-1</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />

* 2DFA: at least <math>\frac{2^{\Omega(n)}}{\log m}</math> and at most <math>2m^{m+1}\cdot 2^{n^{n+1}}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008">{{cite journal|last1=Jirásková|first1=Galina|title=DevelopmentsOn inthe LanguageState Complexity Theoryof Operations on Two-Way Finite Automata|last2=Okhotin|first2=Alexander|volume=5257|year=2008|pages=443–454|issn=0302-9743|doi=10.1007/978-3-540-85780-8_35|chapter=On the State Complexity of Operations on Two-Way Finite Automata|series=Lecture Notes in Computer Science|isbn=978-3-540-85779-2}}</ref>

===Kleene star===