State complexity

From HandWiki
Revision as of 17:55, 8 February 2024 by Jworkorg (talk | contribs) (correction)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata. The classical result in the area is that simulating an [math]\displaystyle{ n }[/math]-state nondeterministic finite automaton by a deterministic finite automaton requires exactly [math]\displaystyle{ 2^n }[/math] states in the worst case.

Transformation between variants of finite automata

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 [math]\displaystyle{ f }[/math] where [math]\displaystyle{ f(n) }[/math] is the least number of states in automata of the second type sufficient to recognize every language recognized by an [math]\displaystyle{ n }[/math]-state automaton of the first type. The following results are known.

  • NFA to DFA: [math]\displaystyle{ 2^n }[/math] states. This is the subset construction by Rabin and Scott,[1] proved optimal by Lupanov.[2]
  • UFA to DFA: [math]\displaystyle{ 2^n }[/math] states, see Leung,[3] An earlier lower bound by Schmidt[4] was smaller.
  • NFA to UFA: [math]\displaystyle{ 2^n-1 }[/math] states, see Leung.[3] There was an earlier smaller lower bound by Schmidt.[4]
  • SVFA to DFA: [math]\displaystyle{ \Theta(3^{n/3}) }[/math] states, see Jirásková and Pighizzini[5]
  • 2DFA to DFA: [math]\displaystyle{ n(n^n-(n-1)^n) }[/math] 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: [math]\displaystyle{ \binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}}) }[/math], see Kapoutsis.[6] Earlier construction by Birget[9] used more states.
  • 2NFA to NFA: [math]\displaystyle{ \binom{2n}{n+1} }[/math], see Kapoutsis.[6]
    • 2NFA to NFA accepting the complement: [math]\displaystyle{ O(4^n) }[/math] states, see Vardi.[10]
  • AFA to DFA: [math]\displaystyle{ 2^{2^n} }[/math] states, see Chandra, Kozen and Stockmeyer.[11]
  • AFA to NFA: [math]\displaystyle{ 2^n }[/math] states, see Fellah, Jürgensen and Yu.[12]
  • 2AFA to DFA: [math]\displaystyle{ 2^{n2^n} }[/math], see Ladner, Lipton and Stockmeyer.[13]
  • 2AFA to NFA: [math]\displaystyle{ 2^{\Theta(n \log n)} }[/math], see Geffert and Okhotin.[14]

The 2DFA vs. 2NFA problem and logarithmic space

Question, Web Fundamentals.svg Unsolved problem in computer science:
Does every [math]\displaystyle{ n }[/math]-state 2NFA have an equivalent [math]\displaystyle{ \operatorname{poly}(n) }[/math]-state 2DFA?
(more unsolved problems in computer science)

It is an open problem whether all 2NFAs can be converted to 2DFAs with polynomially many states, i.e. whether there is a polynomial [math]\displaystyle{ p(n) }[/math] such that for every [math]\displaystyle{ n }[/math]-state 2NFA there exists a [math]\displaystyle{ p(n) }[/math]-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 problem and 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 [math]\displaystyle{ \circ }[/math] and a family of automata X (DFA, NFA, etc.), the state complexity of [math]\displaystyle{ \circ }[/math] is an integer function [math]\displaystyle{ f(m,n) }[/math] such that

  • for each m-state X-automaton A and n-state X-automaton B there is an [math]\displaystyle{ f(m,n) }[/math]-state X-automaton for [math]\displaystyle{ L(A) \circ L(B) }[/math], 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 [math]\displaystyle{ L(A) \circ L(B) }[/math] must have at least [math]\displaystyle{ f(m,n) }[/math] 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 [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 [math]\displaystyle{ L_1 }[/math] requires m states and language [math]\displaystyle{ L_2 }[/math] requires n states, how many states does [math]\displaystyle{ L_1 \cup L_2 }[/math] require?

  • DFA: [math]\displaystyle{ mn }[/math] states, see Maslov[18] and Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ m+n+1 }[/math] states, see Holzer and Kutrib.[20]
  • UFA: between [math]\displaystyle{ mn+m+n }[/math] and [math]\displaystyle{ m + nm 2^{0.79m} }[/math] states, see Jirásek, Jirásková and Šebej.[21]
  • SVFA: [math]\displaystyle{ mn }[/math] states, see Jirásek, Jirásková and Szabari.[22]
  • 2DFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ 4m+n+4 }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: [math]\displaystyle{ m+n }[/math] states, see Kunc and Okhotin.[24]

Intersection

How many states does [math]\displaystyle{ L_1 \cap L_2 }[/math] require?

  • DFA: [math]\displaystyle{ mn }[/math] states, see Maslov[18] and Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ mn }[/math] states, see Holzer and Kutrib.[20]
  • UFA: [math]\displaystyle{ mn }[/math] states, see Jirásek, Jirásková and Šebej.[21]
  • SVFA: [math]\displaystyle{ mn }[/math] states, see Jirásek, Jirásková and Szabari.[22]
  • 2DFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ m+n+1 }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ m+n+1 }[/math] states, see Kunc and Okhotin.[24]

Complementation

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

  • DFA: [math]\displaystyle{ n }[/math] states, by exchanging accepting and rejecting states.
  • NFA: [math]\displaystyle{ 2^n }[/math] states, see Birget.[25]
  • UFA: at least [math]\displaystyle{ n^{\tilde{\Omega}(\log n)} }[/math] states, see Göös, Kiefer and Yuan,[26] and at most [math]\displaystyle{ \sqrt{n+1} \cdot 2^{0.5n} }[/math] states, see Indzhev and Kiefer.[27]
  • SVFA: [math]\displaystyle{ n }[/math] states, by exchanging accepting and rejecting states.
  • 2DFA: at least [math]\displaystyle{ n }[/math] and at most [math]\displaystyle{ 4n }[/math] states, see Geffert, Mereghetti and Pighizzini.[28]

Concatenation

How many states does [math]\displaystyle{ L_1 L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\} }[/math] require?

  • DFA: [math]\displaystyle{ m \cdot 2^n - 2^{n-1} }[/math] states, see Maslov [18] and Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ m+n }[/math] states, see Holzer and Kutrib.[20]
  • UFA: [math]\displaystyle{ \frac{3}{4} 2^{m+n}-1 }[/math] states, see Jirásek, Jirásková and Šebej.[21]
  • SVFA: [math]\displaystyle{ \Theta(3^{n/3}2^m) }[/math] states, see Jirásek, Jirásková and Szabari.[22]
  • 2DFA: at least [math]\displaystyle{ \frac{2^{\Omega(n)}}{\log m} }[/math] and at most [math]\displaystyle{ 2m^{m+1}\cdot 2^{n^{n+1}} }[/math] states, see Jirásková and Okhotin.[29]

Kleene star

  • DFA: [math]\displaystyle{ \frac{3}{4} 2^n }[/math] states, see Maslov[18] and Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ n+1 }[/math] states, see Holzer and Kutrib.[20]
  • UFA: [math]\displaystyle{ \frac{3}{4} 2^n }[/math] states, see Jirásek, Jirásková and Šebej.[21]
  • SVFA: [math]\displaystyle{ \frac{3}{4}2^n }[/math] states, see Jirásek, Jirásková and Szabari.[22]
  • 2DFA: at least [math]\displaystyle{ \frac{1}{n}2^{\frac{n}{2}-1} }[/math] and at most [math]\displaystyle{ 2^{O(n^{n+1})} }[/math] states, see Jirásková and Okhotin.[29]

Reversal

  • DFA: [math]\displaystyle{ 2^n }[/math] states, see Mirkin,[30] Leiss,[31] and Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ n+1 }[/math] states, see Holzer and Kutrib.[20]
  • UFA: [math]\displaystyle{ n }[/math] states.
  • SVFA: [math]\displaystyle{ 2n+1 }[/math] states, see Jirásek, Jirásková and Szabari.[22]
  • 2DFA: between [math]\displaystyle{ n+1 }[/math] and [math]\displaystyle{ n+2 }[/math] states, see Jirásková and Okhotin.[29]

Finite automata over a unary alphabet

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

Let [math]\displaystyle{ g(n)=e^{\Theta(\sqrt{n \ln n})} }[/math] 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: [math]\displaystyle{ g(n)+O(n^2) }[/math] states, see Chrobak.[32]
  • 2DFA to DFA: [math]\displaystyle{ g(n)+O(n) }[/math] states, see Chrobak[32] and Kunc and Okhotin.[33]
  • 2NFA to DFA: [math]\displaystyle{ O(g(n)) }[/math] states, see Mereghetti and Pighizzini.[34] and Geffert, Mereghetti and Pighizzini.[35]
  • NFA to 2DFA: at most [math]\displaystyle{ O(n^2) }[/math] states, see Chrobak.[32]
  • 2NFA to 2DFA: at most [math]\displaystyle{ n^{O(\log n)} }[/math] states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini.[35]
  • UFA to DFA: [math]\displaystyle{ e^{\Theta(\sqrt[3]{n (\ln n)^2})} }[/math], see Okhotin.[36]
  • NFA to UFA: [math]\displaystyle{ g(n)+O(n^2) }[/math], see Okhotin.[36]

Union

  • DFA: [math]\displaystyle{ mn }[/math] states, see Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ m+n+1 }[/math] states, see Holzer and Kutrib.[20]
  • 2DFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ 2m+n+4 }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: [math]\displaystyle{ m+n }[/math] states, see Kunc and Okhotin.[24]

Intersection

  • DFA: [math]\displaystyle{ mn }[/math] states, see Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ mn }[/math] states, see Holzer and Kutrib.[20]
  • 2DFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ m+n+1 }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: between [math]\displaystyle{ m+n }[/math] and [math]\displaystyle{ m+n+1 }[/math] states, see Kunc and Okhotin.[24]

Complementation

  • DFA: [math]\displaystyle{ n }[/math] states.
  • NFA: [math]\displaystyle{ g(n)+O(n^2) }[/math] states, see Holzer and Kutrib.[20]
  • UFA: at least [math]\displaystyle{ n^{(\log \log \log n)^{\Theta(1)}} }[/math] states, see Raskin,[37] and at most [math]\displaystyle{ e^{\Theta(\sqrt[3]{n (\ln n)^2})} }[/math] states, see Okhotin.[36]
  • 2DFA: at least [math]\displaystyle{ n }[/math] and at most [math]\displaystyle{ 2n+3 }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: at least [math]\displaystyle{ n }[/math] and at most [math]\displaystyle{ O(n^8) }[/math] states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.[28]

Concatenation

  • DFA: [math]\displaystyle{ mn }[/math] states, see Yu, Zhuang and Salomaa.[19]
  • NFA: between [math]\displaystyle{ m+n-1 }[/math] and [math]\displaystyle{ m+n }[/math] states, see Holzer and Kutrib.[20]
  • 2DFA: [math]\displaystyle{ e^{\Theta(\sqrt{(m+n)\log(m+n)})} }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: [math]\displaystyle{ e^{\Theta(\sqrt{(m+n)\log(m+n)})} }[/math] states, see Kunc and Okhotin.[23]

Kleene star

  • DFA: [math]\displaystyle{ (n-1)^2+1 }[/math] states, see Yu, Zhuang and Salomaa.[19]
  • NFA: [math]\displaystyle{ n+1 }[/math] states, see Holzer and Kutrib.[20]
  • UFA: [math]\displaystyle{ (n-1)^2+1 }[/math] states, see Okhotin.[36]
  • 2DFA: [math]\displaystyle{ \Theta((g(n))^2) }[/math] states, see Kunc and Okhotin.[23]
  • 2NFA: [math]\displaystyle{ \Theta(g(n)) }[/math] states, see Kunc and Okhotin.[23]

Further reading

Surveys of state complexity were written by Holzer and Kutrib[38][39] and by Gao et al.[40]

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.

References

  1. ↑ Rabin, M. O.; Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646. 
  2. ↑ Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki 9: 321–326. 
  3. ↑ 3.0 3.1 Leung, Hing (2005). "Descriptional complexity of NFA of different ambiguity". International Journal of Foundations of Computer Science 16 (5): 975–984. doi:10.1142/S0129054105003418. ISSN 0129-0541. 
  4. ↑ 4.0 4.1 Schmidt, Erik M. (1978). Succinctness of Description of Context-Free, Regular and Unambiguous Languages (Ph.D.). Cornell University.
  5. ↑ Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401. 
  6. ↑ 6.0 6.1 6.2 Kapoutsis, Christos (2005). "Removing Bidirectionality from Nondeterministic Finite Automata". Mathematical Foundations of Computer Science 2005. Lecture Notes in Computer Science. 3618. pp. 544–555. doi:10.1007/11549345_47. ISBN 978-3-540-28702-5. 
  7. ↑ Shepherdson, J. C. (1959). "The Reduction of Two-Way Automata to One-Way Automata". IBM Journal of Research and Development 3 (2): 198–200. doi:10.1147/rd.32.0198. ISSN 0018-8646. 
  8. ↑ Moore, F.R. (1971). "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): 1211–1214. doi:10.1109/T-C.1971.223108. ISSN 0018-9340. 
  9. ↑ Birget, Jean-Camille (1993). "State-complexity of finite-state devices, state compressibility and incompressibility". Mathematical Systems Theory 26 (3): 237–269. doi:10.1007/BF01371727. ISSN 0025-5661. 
  10. ↑ Vardi, Moshe Y. (1989). "A note on the reduction of two-way automata to one-way automata". Information Processing Letters 30 (5): 261–264. doi:10.1016/0020-0190(89)90205-6. ISSN 0020-0190. 
  11. ↑ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411. 
  12. ↑ Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata∗". International Journal of Computer Mathematics 35 (1–4): 117–132. doi:10.1080/00207169008803893. ISSN 0020-7160. 
  13. ↑ Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating Pushdown and Stack Automata". SIAM Journal on Computing 13 (1): 135–155. doi:10.1137/0213010. ISSN 0097-5397. 
  14. ↑ Geffert, Viliam; Okhotin, Alexander (2014). Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata. Lecture Notes in Computer Science. 8634. pp. 291–302. doi:10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. 
  15. ↑ Sakoda, William J.; Sipser, Michael (1978). "Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78". STOC 1978. ACM. pp. 275–286. doi:10.1145/800133.804357. 
  16. ↑ Berman, Piotr; Lingas, Andrzej (1977). "On the complexity of regular languages in terms of finite automata". Report 304. Polish Academy of Sciences. 
  17. ↑ Kapoutsis, Christos A. (2014). "Two-Way Automata Versus Logarithmic Space". Theory of Computing Systems 55 (2): 421–447. doi:10.1007/s00224-013-9465-0. 
  18. ↑ 18.0 18.1 18.2 18.3 18.4 Maslov, A. N. (1970). "Estimates of the number of states of finite automata". Soviet Mathematics - Doklady 11: 1373–1375. 
  19. ↑ 19.0 19.1 19.2 19.3 19.4 19.5 19.6 19.7 19.8 19.9 Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai (1994). "The state complexities of some basic operations on regular languages". Theoretical Computer Science 125 (2): 315–328. doi:10.1016/0304-3975(92)00011-F. ISSN 0304-3975. 
  20. ↑ 20.00 20.01 20.02 20.03 20.04 20.05 20.06 20.07 20.08 20.09 20.10 Holzer, Markus; Kutrib, Martin (2003). "Nondeterministic descriptional complexity of regular languages". International Journal of Foundations of Computer Science 14 (6): 1087–1102. doi:10.1142/S0129054103002199. ISSN 0129-0541. http://geb.uni-giessen.de/geb/volltexte/2003/1194/. 
  21. ↑ 21.0 21.1 21.2 21.3 Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). Operations on Unambiguous Finite Automata. Lecture Notes in Computer Science. 9840. pp. 243–255. doi:10.1007/978-3-662-53132-7_20. ISBN 978-3-662-53131-0. 
  22. ↑ 22.0 22.1 22.2 22.3 22.4 Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). Computer Science -- Theory and Applications. Lecture Notes in Computer Science. 9139. pp. 231–261. doi:10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. 
  23. ↑ 23.0 23.1 23.2 23.3 23.4 23.5 23.6 23.7 23.8 Kunc, Michal; Okhotin, Alexander (2012). "State complexity of operations on two-way finite automata over a unary alphabet". Theoretical Computer Science 449: 106–118. doi:10.1016/j.tcs.2012.04.010. ISSN 0304-3975. 
  24. ↑ 24.0 24.1 24.2 24.3 Kunc, Michal; Okhotin, Alexander (2011). "State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata". Fundamenta Informaticae 110 (1–4): 231–239. doi:10.3233/FI-2011-540. 
  25. ↑ Birget, Jean-Camille (1993). "Partial orders on words, minimal elements of regular languages, and state complexity". Theoretical Computer Science 119 (2): 267–291. doi:10.1016/0304-3975(93)90160-U. ISSN 0304-3975. 
  26. ↑ Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 February 2022). "Lower Bounds for Unambiguous Automata via Communication Complexity". arXiv:2109.09155 [cs.FL].
  27. ↑ Indzhev, Emil; Kiefer, Stefan (1 August 2022). "On complementing unambiguous automata and graphs with many cliques and cocliques" (in en). Information Processing Letters 177: 106270. doi:10.1016/j.ipl.2022.106270. ISSN 0020-0190. https://ora.ox.ac.uk/objects/uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54/files/rrj4305198. Retrieved 29 May 2022. 
  28. ↑ 28.0 28.1 Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complementing two-way finite automata". Information and Computation 205 (8): 1173–1187. doi:10.1016/j.ic.2007.01.008. ISSN 0890-5401. 
  29. ↑ 29.0 29.1 29.2 Jirásková, Galina; Okhotin, Alexander (2008). On the State Complexity of Operations on Two-Way Finite Automata. Lecture Notes in Computer Science. 5257. pp. 443–454. doi:10.1007/978-3-540-85780-8_35. ISBN 978-3-540-85779-2. 
  30. ↑ Mirkin, Boris G. (1966). "On dual automata". Cybernetics 2: 6–9. doi:10.1007/bf01072247. 
  31. ↑ Leiss, Ernst (1985). "Succinct representation of regular languages by boolean automata II". Theoretical Computer Science 38: 133–136. doi:10.1016/0304-3975(85)90215-4. ISSN 0304-3975. 
  32. ↑ 32.0 32.1 32.2 32.3 Chrobak, Marek (1986). "Finite automata and unary languages". Theoretical Computer Science 47: 149–158. doi:10.1016/0304-3975(86)90142-8. ISSN 0304-3975. 
  33. ↑ Kunc, Michal; Okhotin, Alexander (2011). Developments in Language Theory. Lecture Notes in Computer Science. 6795. pp. 324–336. doi:10.1007/978-3-642-22321-1_28. ISBN 978-3-642-22320-4. 
  34. ↑ Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimal Simulations between Unary Automata". SIAM Journal on Computing 30 (6): 1976–1992. doi:10.1137/S009753979935431X. ISSN 0097-5397. 
  35. ↑ 35.0 35.1 Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Converting two-way nondeterministic unary automata into simpler automata". Theoretical Computer Science 295 (1–3): 189–203. doi:10.1016/S0304-3975(02)00403-6. ISSN 0304-3975. 
  36. ↑ 36.0 36.1 36.2 36.3 Okhotin, Alexander (2012). "Unambiguous finite automata over a unary alphabet". Information and Computation 212: 15–36. doi:10.1016/j.ic.2012.01.003. ISSN 0890-5401. 
  37. ↑ Raskin, Michael (2018). "A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton". pp. 138:1–138:11. doi:10.4230/LIPIcs.ICALP.2018.138. 
  38. ↑ Holzer, Markus; Kutrib, Martin (2009). "Nondeterministic finite automata — recent results on the descriptional and computational complexity". International Journal of Foundations of Computer Science 20 (4): 563–580. doi:10.1142/S0129054109006747. ISSN 0129-0541. 
  39. ↑ Holzer, Markus; Kutrib, Martin (2011). "Descriptional and computational complexity of finite automata—A survey". Information and Computation 209 (3): 456–470. doi:10.1016/j.ic.2010.11.013. ISSN 0890-5401. 
  40. ↑ Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng (2015). "A Survey on Operational State Complexity". arXiv:1509.03254v1 [cs.FL].



Retrieved from "https://handwiki.org/wiki/index.php?title=State_complexity&oldid=3430601"