State complexity explained

State complexity is an area of theoretical computer sciencedealing with the size of abstract automata,such as different kinds of finite automata.The classical result in the area is thatsimulating an

-statenondeterministic finite automatonby a deterministic finite automatonrequires exactly

2ⁿ

states in the worst case.

Transformation between variants of finite automata

Finite automata can bedeterministic andnondeterministic,one-way (DFA, NFA)and two-way(2DFA, 2NFA).Other related classes areunambiguous (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 automatanecessary 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 themis an integer function

where

f(n)

is the least number of states in automata of the second typesufficient to recognize every languagerecognized by an

-state automaton of the first type.The following results are known.

NFA to DFA:

2ⁿ

states. This is the subset construction by Rabin and Scott,^[1] proved optimal by Lupanov.^[2]

UFA to DFA:

2ⁿ

states, see Leung,^[3] An earlier lower bound by Schmidt^[4] was smaller.

NFA to UFA:

2^n-1

states, see Leung. There was an earlier smaller lower bound by Schmidt.

SVFA to DFA:

\Theta(3^n/3)

states, see Jirásková and Pighizzini^[5]

2DFA to DFA:

n(n^n-(n-1)ⁿ⁾

states, see Kapoutsis.^[6] Earlier construction by Shepherdson^[7] used more states, and an earlier lower bound by Moore^[8] was smaller.

2DFA to NFA:

\binom{2n}{n+1}=O(

	4ⁿ
	\sqrt{n

}), see Kapoutsis. Earlier construction by Birget^[9] used more states.

2NFA to NFA:

\binom{2n}{n+1}

, see Kapoutsis.

- 2NFA to NFA accepting the complement:

O(4ⁿ⁾

states, see Vardi.^[10]

AFA to DFA:

	2ⁿ
2

states, see Chandra, Kozen and Stockmeyer.^[11]

AFA to NFA:

2ⁿ

states, see Fellah, Jürgensen and Yu.^[12]

2AFA to DFA:

	n2ⁿ
2

, see Ladner, Lipton and Stockmeyer.^[13]

2AFA to NFA:

2^\Theta(n

, see Geffert and Okhotin.^[14]

The 2DFA vs. 2NFA problem and logarithmic space

It is an open problem whether all 2NFAs can be converted to 2DFAswith polynomially many states, i.e. whether there is a polynomial

p(n)

such that for every

-state 2NFAthere exists a

p(n)

-state 2DFA.The problem was raised by Sakoda and Sipser,^[15] who compared it to the P vs. NP problem in the computational complexity theory.Berman and Lingas^[16] discovered a formal relation between this problemand the L vs. NL open problem.This relation was further elaborated by Kapoutsis.^[17]

State complexity of operations for finite automata

Given a binary regularity-preserving operation on languages

\circ

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

\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)\circL(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)\circL(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 DFAswere published by Maslov^[18] and by Yu, Zhuang and Salomaa.^[19] Holzer and Kutrib^[20] pioneered the state complexity of operations on NFA.The known results for basic operations are listed below.

Union

If language

L₁

requires m statesand language

L₂

requires n states,how many states does

L₁\cupL₂

require?

DFA:

states, see Maslov and Yu, Zhuang and Salomaa.

NFA:

m+n+1

states, see Holzer and Kutrib.

UFA: at least

min(n,m)^{\Omega(log(min(n,m)))}

; between

mn+m+n

and

m+nm2^0.79m

states, see Jirásek, Jirásková and Šebej.^[21]

SVFA:

states, see Jirásek, Jirásková and Szabari.^[22]

2DFA: between

m+n

and

4m+n+4

states, see Kunc and Okhotin.^[23]

2NFA:

m+n

states, see Kunc and Okhotin.^[24]

Intersection

How many states does

L₁\capL₂

require?

DFA:

states, see Maslov and Yu, Zhuang and Salomaa.

NFA:

states, see Holzer and Kutrib.

UFA:

states, see Jirásek, Jirásková and Šebej.

SVFA:

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.

Complementation

If language L requires n statesthen how many states does its complement require?

DFA:

states, by exchanging accepting and rejecting states.

NFA:

2ⁿ

states, see Birget.^[25] or Jirásková^[26]

UFA: at least

n^{\tilde{\Omega}(logn)}

states, see Göös, Kiefer and Yuan,^[27] (this follows an earlier bound by Raskin^[28]); and at most

\sqrt{n+1} ⋅ 2^0.5n

states, see Indzhev and Kiefer.^[29]

SVFA:

states, by exchanging accepting and rejecting states.

2DFA: at least

and at most

states, see Geffert, Mereghetti and Pighizzini.^[30]

Concatenation

How many states does

L₁L₂=\{w₁w₂\midw₁\inL_1,w₂\inL_2\}

require?

DFA:

m ⋅ 2ⁿ-2^n-1

states, see Maslov and Yu, Zhuang and Salomaa.

NFA:

m+n

states, see Holzer and Kutrib.

UFA:

	3
	4

2^m+n-1

states, see Jirásek, Jirásková and Šebej.

SVFA:

\Theta(3^n/32^m)

states, see Jirásek, Jirásková and Szabari.

2DFA: at least

	2^\Omega(n)
	logm

and at most

2m^m+1 ⋅

	nⁿ⁺¹
2

states, see Jirásková and Okhotin.^[31]

Kleene star

DFA:

	3
	4

2ⁿ

states, see Maslov and Yu, Zhuang and Salomaa.

NFA:

n+1

states, see Holzer and Kutrib.

UFA:

	3
	4

2ⁿ

states, see Jirásek, Jirásková and Šebej.

SVFA:

	3
	4

2ⁿ

states, see Jirásek, Jirásková and Szabari.

2DFA: at least

	1
	n

	n	-1
	2

and at most

	O(nⁿ⁺¹)
2

states, see Jirásková and Okhotin.

Reversal

DFA:

2ⁿ

states, see Mirkin,^[32] Leiss,^[33] and Yu, Zhuang and Salomaa.

NFA:

n+1

states, see Holzer and Kutrib.

UFA:

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.

Finite automata over a unary alphabet

State complexity of finite automata with a one-letter (unary) alphabet, pioneered by Chrobak,^[34] is different from the multi-letter case.

Let

g(n)=e^{\Theta(\sqrt{n})}

be Landau's function.

Transformation between models

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²⁾

states, see Chrobak.

2DFA to DFA:

g(n)+O(n)

states, see Chrobak and Kunc and Okhotin.^[35]

2NFA to DFA:

O(g(n))

states, see Mereghetti and Pighizzini.^[36] and Geffert, Mereghetti and Pighizzini.^[37]

NFA to 2DFA: at most

O(n²⁾

states, see Chrobak.

2NFA to 2DFA: at most

n^O(log

states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini.

UFA to DFA:

	\Theta(\sqrt[3]{n(lnn)²
e

)}

, see Okhotin.^[38]

NFA to UFA:

g(n)+O(n²⁾

, see Okhotin.

Union

DFA:

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.^[23]

2NFA:

m+n

states, see Kunc and Okhotin.

Intersection

DFA:

states, see Yu, Zhuang and Salomaa.

NFA:

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.

Complementation

DFA:

states.

NFA:

g(n)+O(n²⁾

states, see Holzer and Kutrib.

UFA: at least

	(logloglogn)^\Theta(1)
n

states, see Raskin,^[39] and at most

	\Theta(\sqrt[3]{n(lnn)²
e

)}

states, see Okhotin.

2DFA: at least

and at most

2n+3

states, see Kunc and Okhotin.

2NFA: at least

and at most

O(n⁸⁾

states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.^[30]

Concatenation

DFA:

states, see Yu, Zhuang and Salomaa.

NFA: between

m+n-1

and

m+n

states, see Holzer and Kutrib.

2DFA:

e^{\Theta(\sqrt{(m+n)log(m+n)})}

states, see Kunc and Okhotin.

2NFA:

e^{\Theta(\sqrt{(m+n)log(m+n)})}

states, see Kunc and Okhotin.

Kleene star

DFA:

(n-1)²⁺¹

states, see Yu, Zhuang and Salomaa.

NFA:

n+1

states, see Holzer and Kutrib.

UFA:

(n-1)²⁺¹

states, see Okhotin.

2DFA:

\Theta((g(n))²⁾

states, see Kunc and Okhotin.

2NFA:

\Theta(g(n))

states, see Kunc and Okhotin.

Notes and References

Rabin. M. O.. Scott. D.. Finite Automata and Their Decision Problems. IBM Journal of Research and Development. 3. 2. 1959. 114–125. 0018-8646. 10.1147/rd.32.0114.
Lupanov. Oleg B.. 1963. A comparison of two types of finite sources. Problemy Kibernetiki. 9. 321–326.
Leung. Hing. Descriptional complexity of NFA of different ambiguity. International Journal of Foundations of Computer Science. 16. 5. 2005. 975–984. 0129-0541. 10.1142/S0129054105003418.
Ph.D. . Schmidt . Erik M. . 1978 . Succinctness of Description of Context-Free, Regular and Unambiguous Languages . Cornell University.
Jirásková. Galina. Pighizzini. Giovanni. Optimal simulation of self-verifying automata by deterministic automata. Information and Computation. 209. 3. 2011. 528–535. 0890-5401. 10.1016/j.ic.2010.11.017.
Book: Kapoutsis. Christos. Mathematical Foundations of Computer Science 2005. Lecture Notes in Computer Science. 3618. 2005. 544–555. 0302-9743. 10.1007/11549345_47. 978-3-540-28702-5. Removing Bidirectionality from Nondeterministic Finite Automata.
Shepherdson. J. C.. The Reduction of Two-Way Automata to One-Way Automata. IBM Journal of Research and Development. 3. 2. 1959. 198–200. 0018-8646. 10.1147/rd.32.0198.
Moore. F.R.. On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata. IEEE Transactions on Computers. C-20. 10. 1971. 1211–1214. 0018-9340. 10.1109/T-C.1971.223108. 206618275.
Birget. Jean-Camille. State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory. 26. 3. 1993. 237–269. 0025-5661. 10.1007/BF01371727. 20375279.
Vardi. Moshe Y.. A note on the reduction of two-way automata to one-way automata. Information Processing Letters. 30. 5. 1989. 261–264. 0020-0190. 10.1016/0020-0190(89)90205-6. 10.1.1.60.464.
Chandra. Ashok K.. Kozen. Dexter C.. Stockmeyer. Larry J.. Alternation. Journal of the ACM. 28. 1. 1981. 114–133. 0004-5411. 10.1145/322234.322243. 238863413. free.
Fellah. A.. Jürgensen. H.. Yu. S.. Constructions for alternating finite automata∗. International Journal of Computer Mathematics. 35. 1–4. 1990. 117–132. 0020-7160. 10.1080/00207169008803893.
Ladner. Richard E.. Lipton. Richard J.. Stockmeyer. Larry J.. Alternating Pushdown and Stack Automata. SIAM Journal on Computing. 13. 1. 1984. 135–155. 0097-5397. 10.1137/0213010.
Book: Geffert. Viliam. Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata. Okhotin. Alexander. 8634. 2014. 291–302. 0302-9743. 10.1007/978-3-662-44522-8_25. Lecture Notes in Computer Science. 978-3-662-44521-1.
Nondeterminism and the Size of Two Way Finite Automata. William J.. Sakoda. Michael. Sipser. Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. 1978. STOC 1978. ACM. 275–286. 10.1145/800133.804357. free.
On the complexity of regular languages in terms of finite automata. Piotr. Berman. Andrzej. Lingas. 1977. Report 304. Polish Academy of Sciences.
Kapoutsis. Christos A.. 2014. Two-Way Automata Versus Logarithmic Space. Theory of Computing Systems. 55. 2. 421–447. 10.1007/s00224-013-9465-0. 14808151.
Maslov. A. N.. 1970. Estimates of the number of states of finite automata. Soviet Mathematics - Doklady. 11. 1373–1375.
Yu. Sheng. Zhuang. Qingyu. Salomaa. Kai. The state complexities of some basic operations on regular languages. Theoretical Computer Science. 125. 2. 1994. 315–328. 0304-3975. 10.1016/0304-3975(92)00011-F.
Holzer. Markus. Kutrib. Martin. Nondeterministic descriptional complexity of regular languages. International Journal of Foundations of Computer Science. 14. 6. 2003. 1087–1102. 0129-0541. 10.1142/S0129054103002199. Submitted manuscript.
Book: Jirásek. Jozef. Operations on Unambiguous Finite Automata. Jirásková. Galina. Šebej. Juraj. 9840. 2016. 243–255. 0302-9743. 10.1007/978-3-662-53132-7_20. Lecture Notes in Computer Science. 978-3-662-53131-0.
Book: Jirásek. Jozef Štefan. Computer Science -- Theory and Applications. Jirásková. Galina. Szabari. Alexander. 9139. 2015. 231–261. 0302-9743. 10.1007/978-3-319-20297-6_16. Lecture Notes in Computer Science. 978-3-319-20296-9.
Kunc. Michal. Okhotin. Alexander. State complexity of operations on two-way finite automata over a unary alphabet. Theoretical Computer Science. 449. 2012. 106–118. 0304-3975. 10.1016/j.tcs.2012.04.010. free.
Kunc. Michal. Okhotin. Alexander. State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata . Fundamenta Informaticae. 110. 1–4. 2011. 231–239. 10.3233/FI-2011-540.
Birget. Jean-Camille. Partial orders on words, minimal elements of regular languages, and state complexity. Theoretical Computer Science. 119. 2. 1993. 267–291. 0304-3975. 10.1016/0304-3975(93)90160-U.
Jirásková . Galina . 2005 . State complexity of some operations on binary regular languages . Theoretical Computer Science . en . 330 . 2 . 287–298 . 10.1016/j.tcs.2004.04.011., Theorem 5
Göös . Mika . Kiefer . Stefan . Yuan . Weiqiang . Lower Bounds for Unambiguous Automata via Communication Complexity . 12 February 2022 . cs.FL . 2109.09155.
Raskin . Mikhail . 2018 . A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton . DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 . en . Schloss-Dagstuhl - Leibniz Zentrum für Informatik . 10.4230/LIPIcs.ICALP.2018.138. free .
Indzhev . Emil . Kiefer . Stefan . On complementing unambiguous automata and graphs with many cliques and cocliques . Information Processing Letters . 1 August 2022 . 177 . 106270 . 10.1016/j.ipl.2022.106270 . 234741832 . 29 May 2022 . IndzhevKiefer22 . en . 0020-0190. free . 2105.07470 .
Geffert. Viliam. Mereghetti. Carlo. Pighizzini. Giovanni. Complementing two-way finite automata. Information and Computation. 205. 8. 2007. 1173–1187. 0890-5401. 10.1016/j.ic.2007.01.008. free.
Book: Jirásková. Galina. On the State Complexity of Operations on Two-Way Finite Automata. Okhotin. Alexander. 5257. 2008. 443–454. 0302-9743. 10.1007/978-3-540-85780-8_35. Lecture Notes in Computer Science. 978-3-540-85779-2.
Mirkin. Boris G.. On dual automata. Cybernetics. 2. 1966. 6–9. 10.1007/bf01072247. 123186223.
Leiss. Ernst. Succinct representation of regular languages by boolean automata II. Theoretical Computer Science. 38. 1985. 133–136. 0304-3975. 10.1016/0304-3975(85)90215-4.
Chrobak. Marek. Finite automata and unary languages. Theoretical Computer Science. 47. 1986. 149–158. 0304-3975. 10.1016/0304-3975(86)90142-8.
Book: Kunc. Michal. Developments in Language Theory. Okhotin. Alexander. 6795. 2011. 324–336. 0302-9743. 10.1007/978-3-642-22321-1_28. Lecture Notes in Computer Science. 978-3-642-22320-4. 10.1.1.616.8835.
Mereghetti. Carlo. Pighizzini. Giovanni. Optimal Simulations between Unary Automata. SIAM Journal on Computing. 30. 6. 2001. 1976–1992. 0097-5397. 10.1137/S009753979935431X. 2434/35121. free.
Geffert. Viliam. Mereghetti. Carlo. Pighizzini. Giovanni. Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science. 295. 1–3. 2003. 189–203. 0304-3975. 10.1016/S0304-3975(02)00403-6.
Okhotin. Alexander. Unambiguous finite automata over a unary alphabet. Information and Computation. 212. 2012. 15–36. 0890-5401. 10.1016/j.ic.2012.01.003. free.
Raskin. Michael. A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton. 138:1–138:11. Proc. ICALP 2018. 2018. 10.4230/LIPIcs.ICALP.2018.138. free .
Holzer. Markus. Kutrib. Martin. Nondeterministic finite automata — recent results on the descriptional and computational complexity. International Journal of Foundations of Computer Science. 20. 4. 2009. 563–580. 0129-0541. 10.1142/S0129054109006747.
Holzer. Markus. Kutrib. Martin. Descriptional and computational complexity of finite automata—A survey. Information and Computation. 209. 3. 2011. 456–470. 0890-5401. 10.1016/j.ic.2010.11.013.
1509.03254v1. Gao. Yuan. A Survey on Operational State Complexity. Moreira. Nelma. Reis. Rogério. Yu. Sheng. cs.FL. 2015.

State complexity explained

Transformation between variants of finite automata

The 2DFA vs. 2NFA problem and logarithmic space

State complexity of operations for finite automata

Union

Intersection

Complementation

Concatenation

Kleene star

Reversal

Finite automata over a unary alphabet

Transformation between models

Union

Intersection

Complementation

Concatenation

Kleene star

Further reading

Notes and References