state complexity

Finite automata can be

deterministic and

nondeterministic,

one-way (DFA, NFA)

and two-way

(2DFA, 2NFA).

Other related classes are

unambiguous (UFA),

self-verifying (SVFA)

and alternating (AFA) finite automata.

These automata can also be two-way (2UFA, 2SVFA, 2AFA).

All these machines can accept exactly the regular languages.

However, the size of different types of automata

necessary to accept the same language

(measured in the number of their states)

may be different.

For any two types of finite automata,

the state complexity tradeoff between them

is an integer function $f$

where $f(n)$ is the least number of states in automata of the second type

sufficient to recognize every language

recognized by an $n$-state automaton of the first type.

The following results are known.

• NFA to DFA: $2^n$ states. This is the subset construction by Rabin and Scott,{{cite journal|last1=Rabin|first1=M. O.|last2=Scott|first2=D.|title=Finite Automata and Their Decision Problems|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=114–125|issn=0018-8646|doi=10.1147/rd.32.0114}} proved optimal by Lupanov.{{cite journal

| last = Lupanov

| first = Oleg B.

| date = 1963

| title = A comparison of two types of finite sources

| journal = Problemy Kibernetiki

| volume = 9

| pages = 321–326

}}

• UFA to DFA: $2^n$ states, see Leung,{{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=5|year=2005|pages=975–984|issn=0129-0541|doi=10.1142/S0129054105003418}} An earlier lower bound by Schmidt{{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}} was smaller.
• NFA to UFA: $2^n-1$ states, see Leung. There was an earlier smaller lower bound by Schmidt.
• SVFA to DFA: $\backslash Theta(3^\{n/3\})$ states, see Jirásková and Pighizzini{{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=0890-5401|doi=10.1016/j.ic.2010.11.017}}
• 2DFA to DFA: $n(n^n-(n-1)^n)$ states, see Kapoutsis.{{Cite book|last1=Kapoutsis|first1=Christos|title=Mathematical Foundations of Computer Science 2005|series=Lecture Notes in Computer Science|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47|isbn=978-3-540-28702-5|chapter=Removing Bidirectionality from Nondeterministic Finite Automata}} Earlier construction by Shepherdson{{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}} used more states, and an earlier lower bound by Moore{{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|s2cid=206618275}} was smaller.
• 2DFA to NFA: $\backslash binom\{2n\}\{n+1\}\; =\; O(\backslash frac\{4^n\}\{\backslash sqrt\{n\}\})$, see Kapoutsis. Earlier construction by Birget{{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|s2cid=20375279}} used more states.
• 2NFA to NFA: $\backslash binom\{2n\}\{n+1\}$, see Kapoutsis.
• 2NFA to NFA accepting the complement: $O(4^n)$ states, see Vardi.{{cite journal|last1=Vardi|first1=Moshe Y.|title=A note on the reduction of two-way automata to one-way automata|journal=Information Processing Letters|volume=30|issue=5|year=1989|pages=261–264|issn=0020-0190|doi=10.1016/0020-0190(89)90205-6|citeseerx=10.1.1.60.464}}
• AFA to DFA: $2^\{2^n\}$ states, see Chandra, Kozen and Stockmeyer.{{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=0004-5411|doi=10.1145/322234.322243|s2cid=238863413|doi-access=free}}
• AFA to NFA: $2^n$ states, see Fellah, Jürgensen and Yu.{{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–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}
• 2AFA to DFA: $2^\{n2^n\}$, see Ladner, Lipton and Stockmeyer.{{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}}
• 2AFA to NFA: $2^\{\backslash Theta(n\; \backslash log\; n)\}$, see Geffert and Okhotin.{{Cite book|last1=Geffert|first1=Viliam|title=Transforming Two-Way Alternating Finite Automata to 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|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}

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

It is an open problem whether all 2NFAs can be converted to 2DFAs

with polynomially many states, i.e. whether there is a polynomial $p(n)$

such that for every $n$-state 2NFA

there exists a $p(n)$-state 2DFA.

The problem was raised by Sakoda and Sipser,{{cite conference

| 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

| publisher = ACM

| location =

| pages = 275–286

| doi = 10.1145/800133.804357

| doi-access = free

}}

who compared it to the P vs. NP problem

in the computational complexity theory.

Berman and Lingas{{cite conference

| title = On the complexity of regular languages in terms of finite automata

| first1 = Piotr

| last1 = Berman

| first2 = Andrzej

| last2 = Lingas

| year = 1977

| volume = Report 304

| publisher = Polish Academy of Sciences

}} discovered a formal relation between this problem

and the L vs. NL open problem.

This relation was further elaborated by Kapoutsis.{{cite journal

| last = Kapoutsis

| first = Christos A.

| date = 2014

| title = Two-Way Automata Versus Logarithmic Space

| journal = Theory of Computing Systems

| volume = 55

| issue = 2

| pages = 421–447

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

| s2cid = 14808151

}}

Given a binary regularity-preserving operation on languages $\backslash circ$

and a family of automata X (DFA, NFA, etc.),

the state complexity of $\backslash circ$

is an integer function $f(m,n)$ such that

• for each m-state X-automaton A and n-state X-automaton B there is an $f(m,n)$-state X-automaton for $L(A)\; \backslash circ\; L(B)$, and
• for all integers m, n there is an m-state X-automaton A and an n-state X-automaton B such that every X-automaton for $L(A)\; \backslash circ\; L(B)$ must have at least $f(m,n)$ states.

Analogous definition applies for operations with any number of arguments.

The first results on state complexity of operations for DFAs

were published by Maslov

{{cite journal

| last = Maslov

| first = A. N.

| date = 1970

| title = Estimates of the number of states of finite automata

| journal = Soviet Mathematics - Doklady

| volume = 11

| pages = 1373–1375

}}

and by Yu, Zhuang and Salomaa.

{{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=0304-3975|doi=10.1016/0304-3975(92)00011-F}}

Holzer and Kutrib

{{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=6|year=2003|pages=1087–1102|issn=0129-0541|doi=10.1142/S0129054103002199|url=http://geb.uni-giessen.de/geb/volltexte/2003/1194/|type=Submitted manuscript}}

pioneered the state complexity of operations on NFA.

The known results for basic operations are listed below.

If language $L\_1$ requires m states

and language $L\_2$ requires n states,

how many states does $L\_1\; \backslash cup\; L\_2$ require?

• DFA: $mn$ states, see Maslov and Yu, Zhuang and Salomaa.
• NFA: $m+n+1$ states, see Holzer and Kutrib.
• UFA: at least $\backslash min(n,m)^\{\backslash Omega(\backslash log(\backslash min(n,m)))\}$; between $mn+m+n$ and $m\; +\; nm\; 2^\{0.79m\}$ states, see Jirásek, Jirásková and Šebej.{{Cite book|last1=Jirásek|first1=Jozef|title=Operations on Unambiguous Finite Automata|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|series=Lecture Notes in Computer Science|isbn=978-3-662-53131-0}}
• SVFA: $mn$ states, see Jirásek, Jirásková and Szabari.{{Cite book|last1=Jirásek|first1=Jozef Štefan|title=Computer Science -- Theory and Applications|last2=Jirásková|first2=Galina|last3=Szabari|first3=Alexander|volume=9139|year=2015|pages=231–261|issn=0302-9743|doi=10.1007/978-3-319-20297-6_16|series=Lecture Notes in Computer Science|isbn=978-3-319-20296-9}}
• 2DFA: between $m+n$ and $4m+n+4$ states, see Kunc and Okhotin.{{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=0304-3975|doi=10.1016/j.tcs.2012.04.010|doi-access=free}}
• 2NFA: $m+n$ states, see Kunc and Okhotin.{{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|issue=1–4|year=2011|pages=231–239|doi=10.3233/FI-2011-540}}

How many states does $L\_1\; \backslash cap\; L\_2$ require?

• DFA: $mn$ states, see Maslov and Yu, Zhuang and Salomaa.
• NFA: $mn$ states, see Holzer and Kutrib.
• UFA: $mn$ states, see Jirásek, Jirásková and Šebej.
• SVFA: $mn$ states, see Jirásek, Jirásková and Szabari.
• 2DFA: between $m+n$ and $m+n+1$ states, see Kunc and Okhotin.
• 2NFA: between $m+n$ and $m+n+1$ states, see Kunc and Okhotin.

If language L requires n states

then how many states does its complement require?

• DFA: $n$ states, by exchanging accepting and rejecting states.
• NFA: $2^n$ states, see Birget.{{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}} or Jirásková{{Cite journal |last=Jirásková |first=Galina |date=2005 |title=State complexity of some operations on binary regular languages |url=https://linkinghub.elsevier.com/retrieve/pii/S0304397504006577 |journal=Theoretical Computer Science |language=en |volume=330 |issue=2 |pages=287–298 |doi=10.1016/j.tcs.2004.04.011}}, Theorem 5
• UFA: at least $n^\{\backslash tilde\{\backslash Omega\}(\backslash log\; n)\}$ states, see Göös, Kiefer and Yuan,{{cite 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 |class=cs.FL |eprint=2109.09155}} (this follows an earlier bound by Raskin{{Cite journal |last=Raskin |first=Mikhail |date=2018 |title=A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 |language=en |publisher=Schloss-Dagstuhl - Leibniz Zentrum für Informatik |doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }}); and at most $\backslash sqrt\{n+1\}\; \backslash cdot\; 2^\{0.5n\}$ states, see Indzhev and Kiefer.{{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://ora.ox.ac.uk/objects/uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54/files/rrj4305198 |access-date=29 May 2022 |ref=IndzhevKiefer22 |language=en |issn=0020-0190|doi-access=free |arxiv=2105.07470 }}
• SVFA: $n$ states, by exchanging accepting and rejecting states.
• 2DFA: at least $n$ and at most $4n$ states, see Geffert, Mereghetti and Pighizzini.{{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|doi-access=free}}

How many states does $L\_1\; L\_2\; =\; \backslash \{w\_1\; w\_2\; \backslash mid\; w\_1\; \backslash in\; L\_1,\; w\_2\; \backslash in\; L\_2\backslash \}$ require?

• DFA: $m\; \backslash cdot\; 2^n\; -\; 2^\{n-1\}$ states, see Maslov and Yu, Zhuang and Salomaa.
• NFA: $m+n$ states, see Holzer and Kutrib.
• UFA: $\backslash frac\{3\}\{4\}\; 2^\{m+n\}-1$ states, see Jirásek, Jirásková and Šebej.
• SVFA: $\backslash Theta(3^\{n/3\}2^m)$ states, see Jirásek, Jirásková and Szabari.
• 2DFA: at least $\backslash frac\{2^\{\backslash Omega(n)\}\}\{\backslash log\; m\}$ and at most $2m^\{m+1\}\backslash cdot\; 2^\{n^\{n+1\}\}$ states, see Jirásková and Okhotin.{{Cite book|last1=Jirásková|first1=Galina|title=On the State Complexity of 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|series=Lecture Notes in Computer Science|isbn=978-3-540-85779-2}}

• DFA: $\backslash frac\{3\}\{4\}\; 2^n$ states, see Maslov and Yu, Zhuang and Salomaa.
• NFA: $n+1$ states, see Holzer and Kutrib.
• UFA: $\backslash frac\{3\}\{4\}\; 2^n$ states, see Jirásek, Jirásková and Šebej.
• SVFA: $\backslash frac\{3\}\{4\}2^n$ states, see Jirásek, Jirásková and Szabari.
• 2DFA: at least $\backslash frac\{1\}\{n\}2^\{\backslash frac\{n\}\{2\}-1\}$ and at most $2^\{O(n^\{n+1\})\}$ states, see Jirásková and Okhotin.

• DFA: $2^n$ states, see Mirkin,{{cite journal|last1=Mirkin|first1=Boris G.|title=On dual automata|journal=Cybernetics|volume=2|year=1966|pages=6–9|doi=10.1007/bf01072247|s2cid=123186223}} Leiss,{{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}} and Yu, Zhuang and Salomaa.
• NFA: $n+1$ states, see Holzer and Kutrib.
• UFA: $n$ states.
• SVFA: $2n+1$ states, see Jirásek, Jirásková and Szabari.
• 2DFA: between $n+1$ and $n+2$ states, see Jirásková and Okhotin.

State complexity of finite automata with a one-letter (unary) alphabet, pioneered by Chrobak,{{cite journal|last1=Chrobak|first1=Marek|title=Finite automata and unary languages|journal=Theoretical Computer Science|volume=47|year=1986|pages=149–158|issn=0304-3975|doi=10.1016/0304-3975(86)90142-8}} is different from the multi-letter case.

Let $g(n)=e^\{\backslash Theta(\backslash sqrt\{n\; \backslash ln\; n\})\}$ be Landau's function.

For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case.

• NFA to DFA: $g(n)+O(n^2)$ states, see Chrobak.
• 2DFA to DFA: $g(n)+O(n)$ states, see Chrobak and Kunc and Okhotin.{{Cite book|last1=Kunc|first1=Michal|title=Developments in Language Theory|last2=Okhotin|first2=Alexander|volume=6795|year=2011|pages=324–336|issn=0302-9743|doi=10.1007/978-3-642-22321-1_28|series=Lecture Notes in Computer Science|isbn=978-3-642-22320-4|citeseerx=10.1.1.616.8835}}
• 2NFA to DFA: $O(g(n))$ states, see Mereghetti and Pighizzini.{{cite journal|last1=Mereghetti|first1=Carlo|last2=Pighizzini|first2=Giovanni|title=Optimal Simulations between Unary Automata|journal=SIAM Journal on Computing|volume=30|issue=6|year=2001|pages=1976–1992|issn=0097-5397|doi=10.1137/S009753979935431X|hdl=2434/35121|hdl-access=free}} and Geffert, Mereghetti and Pighizzini.{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Converting two-way nondeterministic unary automata into simpler automata|journal=Theoretical Computer Science|volume=295|issue=1–3|year=2003|pages=189–203|issn=0304-3975|doi=10.1016/S0304-3975(02)00403-6}}
• NFA to 2DFA: at most $O(n^2)$ states, see Chrobak.
• 2NFA to 2DFA: at most $n^\{O(\backslash log\; n)\}$ states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini.
• UFA to DFA: $e^\{\backslash Theta(\backslash sqrt[3]\{n\; (\backslash ln\; n)^2\})\}$, see Okhotin.{{cite journal|last1=Okhotin|first1=Alexander|title=Unambiguous finite automata over a unary alphabet|journal=Information and Computation|volume=212|year=2012|pages=15–36|issn=0890-5401|doi=10.1016/j.ic.2012.01.003|doi-access=free}}
• NFA to UFA: $g(n)+O(n^2)$, see Okhotin.

• DFA: $mn$ states, see Yu, Zhuang and Salomaa.
• NFA: $m+n+1$ states, see Holzer and Kutrib.
• 2DFA: between $m+n$ and $2m+n+4$ states, see Kunc and Okhotin.
• 2NFA: $m+n$ states, see Kunc and Okhotin.

• DFA: $mn$ states, see Yu, Zhuang and Salomaa.
• NFA: $mn$ states, see Holzer and Kutrib.
• 2DFA: between $m+n$ and $m+n+1$ states, see Kunc and Okhotin.
• 2NFA: between $m+n$ and $m+n+1$ states, see Kunc and Okhotin.

• DFA: $n$ states.
• NFA: $g(n)+O(n^2)$ states, see Holzer and Kutrib.
• UFA: at least $n^\{(\backslash log\; \backslash log\; \backslash log\; n)^\{\backslash Theta(1)\}\}$ states, see Raskin,{{cite conference |last1=Raskin|first1=Michael|title=A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton|pages=138:1–138:11|book-title=Proc. ICALP 2018|year=2018|doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }} and at most $e^\{\backslash Theta(\backslash sqrt[3]\{n\; (\backslash ln\; n)^2\})\}$ states, see Okhotin.
• 2DFA: at least $n$ and at most $2n+3$ states, see Kunc and Okhotin.
• 2NFA: at least $n$ and at most $O(n^8)$ states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.

• DFA: $mn$ states, see Yu, Zhuang and Salomaa.
• NFA: between $m+n-1$ and $m+n$ states, see Holzer and Kutrib.
• 2DFA: $e^\{\backslash Theta(\backslash sqrt\{(m+n)\backslash log(m+n)\})\}$ states, see Kunc and Okhotin.
• 2NFA: $e^\{\backslash Theta(\backslash sqrt\{(m+n)\backslash log(m+n)\})\}$ states, see Kunc and Okhotin.

• DFA: $(n-1)^2+1$ states, see Yu, Zhuang and Salomaa.
• NFA: $n+1$ states, see Holzer and Kutrib.
• UFA: $(n-1)^2+1$ states, see Okhotin.
• 2DFA: $\backslash Theta((g(n))^2)$ states, see Kunc and Okhotin.
• 2NFA: $\backslash Theta(g(n))$ states, see Kunc and Okhotin.

Surveys of state complexity

were written by Holzer and Kutrib{{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}}{{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=0890-5401|doi=10.1016/j.ic.2010.11.013}}

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}}

New research on state complexity

is commonly presented at the annual workshops on

Descriptional Complexity of Formal Systems (DCFS),

at the

Conference on Implementation and Application of Automata (CIAA),

and at various conferences on theoretical computer science in general.

{{reflist}}

Category:Finite-state machines