State complexity: Difference between revisions

Revision as of 20:00, 22 March 2017

Revision as of 20:19, 22 March 2017

Line 46:

}}</ref>

* UFA to DFA: <math>2^n</math> states, see [[Hing Leung|Leung]],<ref name="Leung2005">{{cite journal|last1=Leung|first1=Hing|title=Descriptional complexity of NFA of different ambiguity|journal=International Journal of Foundations of Computer Science|volume=16|issue=055|year=2005|pages=975–984|issn=0129-0541|doi=10.1142/S0129054105003418}}</ref> An earlier lower bound by Schmidt<ref name="Schmidt1978">{{cite thesis |type=Ph.D. |last=Schmidt |first=Erik M. |date=1978 |title=Succinctness of Description of Context-Free, Regular and Unambiguous Languages |publisher=Cornell University}}</ref> was smaller.

* NFA to UFA: <math>2^n-1</math> states, see Leung.<ref name="Leung2005" /> There was an earlier smaller lower bound by Schmidt.<ref name="Schmidt1978" />

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=RemovingMathematical BidirectionalityFoundations fromof NondeterministicComputer FiniteScience Automata2005|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 61:

* AFA to DFA: <math>2^{2^n}</math> states, see [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=00045411|doi=10.1145/322234.322243}}</ref>

* AFA to NFA: <math>2^n</math> states, see Fellah, Jürgensen and Yu.<ref name="FellahJürgensen1990">{{cite journal|last1=Fellah|first1=A.|last2=Jürgensen|first2=H.|last3=Yu|first3=S.|title=Constructions for alternating finite automata∗|journal=International Journal of Computer Mathematics|volume=35|issue=1-41–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}</ref>

* 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|last2=Okhotin|first2=Alexander|title=TransformingMathematical Two-WayFoundations Alternatingof FiniteComputer AutomataScience to One-Way Nondeterministic Automata2014|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==

Line 84:

| publisher = ACM

| ___location =

| pages = 275-286275–286

| doi = 10.1145/800133.804357

}}</ref>,

Line 108:

| volume = 55

| issue = 2

| pages = 421-447421–447

| doi = 10.1007/s00224-013-9465-0

}}</ref>

Line 134:

| journal = Soviet Mathematics Doklady

| volume = 11

| pages = 1373-13751373–1375

}}</ref>

and by Yu, Zhuang and [[Kai Salomaa|Salomaa]].

<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=NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES|journal=International Journal of Foundations of Computer Science|volume=14|issue=066|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=Developments in Language Theory|last2=Jirásková|first2=Galina|last3=Šebej|first3=Juraj|title=Operations on Unambiguous Finite Automata|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>

* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata |journal=Fundamenta Informaticae|volume=110|year=2011|pages=231-239231–239|doi=10.3233/FI-2011-540|doi-broken-date=2017-03-22}}</ref>

===Intersection===

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=Developments in Language Theory|last2=Okhotin|first2=Alexander|title=On the State Complexity of Operations on Two-Way Finite Automata|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===

Line 224:

was written by Yu.-->

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=044|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.{{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}}

and by Gao et al.{{cite arxiv| arxiv=1509.03254v1}}

New research on state complexity