pith. sign in

arxiv: 2301.03708 · v4 · submitted 2023-01-09 · 💻 cs.FL

Descriptional Complexity of Finite Automata -- Selected Highlights

Arto Salomaa , Kai Salomaa , Taylor J. Smith This is my paper

Pith reviewed 2026-05-24 09:39 UTC · model grok-4.3

classification 💻 cs.FL
keywords state complexityoperational state complexityfinite automatanondeterministic automataregular languagesdescriptional complexitymarked concatenationuncomputability
0
0 comments X

The pith

The state complexity of languages obtained from general combinations of regularity-preserving operations is uncomputable when those combinations include intersection and marked concatenation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This review paper examines descriptional complexity results for finite automata, centering on state complexity and nondeterministic state complexity of regular languages. It covers size comparisons across automaton types and non-recursive trade-offs when regular languages are described by more powerful mechanisms such as context-free grammars. The core focus is operational state complexity, which tracks how the minimal automaton size changes after applying sequences of operations that preserve regularity. The paper shows that computing this size becomes impossible for broad classes of operation combinations that contain both intersection and marked concatenation. Such uncomputability reveals hard limits on algorithmic determination of automaton sizes for composed languages.

Core claim

Operational state complexity studies the number of states needed for the minimal automaton accepting the language that results from a regularity-preserving operation, expressed as a function of the state complexities of the input languages. For general combinations of such operations that include intersection and marked concatenation, determining the resulting state complexity is uncomputable.

What carries the argument

Operational state complexity, which measures the state complexity of the language resulting from a regularity-preserving operation as a function of the complexities of the argument languages.

If this is right

  • No algorithm exists to compute the minimal number of states after arbitrary sequences of operations that mix intersection with marked concatenation.
  • State-complexity functions for such combined operations lie outside the recursive functions.
  • Non-recursive trade-offs appear when regular languages are described by automata versus context-free grammars in the presence of these operations.
  • Specific pairs of operations can be chosen so that their joint effect on state complexity remains decidable, but adding further operations quickly renders the problem undecidable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical tools that compute state complexity must therefore restrict attention to narrow, fixed sets of operations rather than allowing arbitrary combinations.
  • The uncomputability result may interact with decidability questions for other automata problems such as equivalence or inclusion after the same operation sequences.
  • One could test whether removing marked concatenation restores computability while keeping intersection, or vice versa.

Load-bearing premise

The operations under consideration preserve regularity, so that the result is always a regular language with a finite-automaton description.

What would settle it

An algorithm that, given any finite collection of regularity-preserving operations including intersection and marked concatenation together with automata for the argument languages, outputs the exact state complexity of the resulting language.

read the original abstract

The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper surveys selected highlights in the descriptional complexity of finite automata. It covers the state complexity and nondeterministic state complexity of regular languages, size comparisons among NFAs of varying ambiguity, non-recursive trade-offs between finite automata and more powerful mechanisms such as context-free grammars, and operational state complexity for regularity-preserving operations. It states that determining the state complexity of combined operations is generally challenging and uncomputable for general combinations that include intersection and marked concatenation.

Significance. As a survey compiling established results from the literature, the manuscript serves as a reference for researchers in automata theory by organizing key facts on state complexity measures and explicitly noting uncomputability results that delineate computational boundaries for operational state complexity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the accurate summary of the manuscript's content, and the recommendation to accept. The paper is intended as a concise survey of selected highlights rather than an exhaustive treatment.

Circularity Check

0 steps flagged

Survey paper with no internal derivations or load-bearing steps

full rationale

This is a survey compiling known results on descriptional complexity. The abstract states the uncomputability of state complexity for general combinations of regularity-preserving operations as an established fact, without deriving it. No equations, proofs, or new claims appear that could reduce to self-definition, fitted inputs, or self-citation chains. All referenced results are external and the paper makes no attempt to prove or unify them internally.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Survey paper; no free parameters, axioms, or invented entities introduced by the authors.

pith-pipeline@v0.9.0 · 5663 in / 1054 out tokens · 29874 ms · 2026-05-24T09:39:38.489050+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages

  1. [1]

    On G¨ odel speed-up and succinctness of lang uage representations

    Hartmanis J. On G¨ odel speed-up and succinctness of lang uage representations. Theoretical Computer Science, 1983. 26(3):335–342. doi:10.1016/0304-3975(83)90016-6

    work page doi:10.1016/0304-3975(83)90016-6 1983

  2. [2]

    A comparison of two types of finite sources (O s ravnenii dvukh tipov konechnykh is- tochnikov)

    Lupanov OB. A comparison of two types of finite sources (O s ravnenii dvukh tipov konechnykh is- tochnikov). Problemy Kibernetiki, 1963. 9:321–326

    work page 1963

  3. [3]

    Estimates of the number of states of finite auto mata

    Maslov AN. Estimates of the number of states of finite auto mata. Soviet Math. Dokl. , 1970. 11(5):1373– 1375

    work page 1970

  4. [4]

    The Recursive Equivalence of the Reachability Problem and the Liveness Problem for Petri Nets and Vector Addition Systems

    Meyer AR, Fischer MJ. Economy of description by automata , grammars, and formal systems. In: Pro- ceedings of SW A T 1971. IEEE, 1971 pp. 188–191. doi:10.1109/SW A T.1971.11. 236 A. Salomaa et al. / Descriptional Complexity – Highlights

    work page doi:10.1109/sw 1971

  5. [5]

    On the bounds for state-set size in the proofs of equivalence between deterministic, non- deterministic, and two-way finite automata

    Moore FR. On the bounds for state-set size in the proofs of equivalence between deterministic, non- deterministic, and two-way finite automata. IEEE Trans. Comput. , 1971. C-20(10):1211–1214. doi: 10.1109/T-C.1971.223108

    work page doi:10.1109/t-c.1971.223108 1971

  6. [6]

    A regularity test for pushdown machines

    Stearns RE. A regularity test for pushdown machines. Information and Control , 1967. 11(3):323–340. doi:10.1016/S0019-9958(67)90591-8

    work page doi:10.1016/s0019-9958(67)90591-8 1967

  7. [7]

    Nondeterminism and the size of two wa y finite automata

    Sakoda WJ, Sipser M. Nondeterminism and the size of two wa y finite automata. In: Proceedings of STOC

    work page

  8. [8]

    ACM, 1978 pp. 275–286. doi:10.1145/800133.804357

    work page doi:10.1145/800133.804357 1978

  9. [9]

    Pebbling Moutain Ranges and its Applica tion of DCFL-Recognition

    Berman P . A note on sweeping automata. In: Proceedings of ICALP 1980, volume 85 of LNCS. Springer, 1980 pp. 91–97. doi:10.1007/3-540-10003-2 62

    work page doi:10.1007/3-540-10003-2 1980

  10. [10]

    Lower bounds on the size of sweeping automata

    Sipser M. Lower bounds on the size of sweeping automata. Journal of Computer and System Sciences ,

    work page

  11. [11]

    doi:10.1016/0022-0000(80)90034-3

    21(2):195–202. doi:10.1016/0022-0000(80)90034-3

    work page doi:10.1016/0022-0000(80)90034-3

  12. [12]

    Simple linear work suffix arr ay construction

    Hromkoviˇ c J, Schnitger G. Nondeterminism versus determinism for two-way finite automata: Generaliza- tions of Sipser’s separation. In: Proceedings of ICALP 2003 , volume 2719 of LNCS. Springer, 2003 pp. 439–451. doi:10.1007/3-540-45061-0 36

    work page doi:10.1007/3-540-45061-0 2003

  13. [13]

    Two-way automata versus logarithmic spa ce

    Kapoutsis CA. Two-way automata versus logarithmic spa ce. Theory of Computing Systems, 2014. 55:421–

    work page 2014

  14. [14]

    doi:10.1007/s00224-013-9465-0

    work page doi:10.1007/s00224-013-9465-0

  15. [15]

    Two-way finite automata: Old and recent re sults

    Pighizzini G. Two-way finite automata: Old and recent re sults. Fundamenta Informaticae, 2013. 126(2– 3):225–246. doi:10.3233/FI-2013-879

    work page doi:10.3233/fi-2013-879 2013

  16. [16]

    A survey on operational sta te complexity

    Gao Y , Moreira N, Reis R, Y u S. A survey on operational sta te complexity. Journal of Automata, Lan- guages and Combinatorics , 2017. 21(4):251–310. doi:10.25596/jalc-2016-251

    work page doi:10.25596/jalc-2016-251 2017

  17. [17]

    Descriptional complexity of machines with limited resources

    Goldstine J, Kappes M, Kintala CMR, Leung H, Malcher A, W otschke D. Descriptional complexity of machines with limited resources. Journal of Universal Computer Science , 2002. 8(2):193–234. doi: 10.3217/jucs-008-02-0193

    work page doi:10.3217/jucs-008-02-0193 2002

  18. [18]

    From finite automata to regular expre ssions and back — A summary on descriptional complexity

    Gruber H, Holzer M. From finite automata to regular expre ssions and back — A summary on descriptional complexity. International Journal of F oundations of Computer Science , 2015. 26(8):1009–1040. doi: 10.1142/S0129054115400110

    work page doi:10.1142/s0129054115400110 2015

  19. [19]

    Descriptional complexity of regular languages

    Gruber H, Holzer M, Kutrib M. Descriptional complexity of regular languages. In: Pin J ´E (ed.), Handbook of Automata Theory, volume 1, pp. 411–457. EMS Press, 2021. d oi:10.4171/AUTOMA TA-1/12

    work page doi:10.4171/automa 2021

  20. [20]

    Descriptional and computational co mplexity of finite automata—A survey

    Holzer M, Kutrib M. Descriptional and computational co mplexity of finite automata—A survey. Infor- mation and Computation , 2011. 209(3):456–470. doi:10.1016/j.ic.2010.11.013

    work page doi:10.1016/j.ic.2010.11.013 2011

  21. [21]

    Descriptional complexity of finite autom ata: Concepts and open problems

    Hromkoviˇ c J. Descriptional complexity of finite autom ata: Concepts and open problems. Journal of Automata, Languages and Combinatorics , 2002. 7(4):519–531. doi:10.25596/jalc-2002-519

    work page doi:10.25596/jalc-2002-519 2002

  22. [22]

    Regular languages

    Y u S. Regular languages. In: Rozenberg G, Salomaa A (eds .), Handbook of Formal Languages, volume 1, pp. 41–110. Springer, 1997. doi:10.1007/978-3-642-59136 -5 2

    work page doi:10.1007/978-3-642-59136 1997

  23. [23]

    On the succinctness of different represen tations of languages

    Hartmanis J. On the succinctness of different represen tations of languages. SIAM Journal of Computing ,

    work page

  24. [24]

    doi:10.1137/0209010

    9(1):114–120. doi:10.1137/0209010

    work page doi:10.1137/0209010

  25. [25]

    Context-free languages and Turing machin e computations

    Hartmanis J. Context-free languages and Turing machin e computations. In: Mathematical Aspects of Computer Science, volume 19 of Proc. Sympos. Appl. Math. American Mathematical Society, 1967 pp. 42–51. doi:10.1090/psapm/019/0235938. A. Salomaa et al. / Descriptional Complexity – Highlights 237

    work page doi:10.1090/psapm/019/0235938 1967

  26. [26]

    The phenomenon of non-recursive trade-offs

    Kutrib M. The phenomenon of non-recursive trade-offs. International Journal of F oundations of Computer Science, 2005. 16(5):957–973. doi:10.1142/S0129054105003406

    work page doi:10.1142/s0129054105003406 2005

  27. [27]

    Succinctness of descriptions of context-f ree, regular, and finite languages

    Schmidt EM. Succinctness of descriptions of context-f ree, regular, and finite languages. Ph.D. thesis, Cornell University, 1978

    work page 1978

  28. [28]

    Succinct representation of regular languages by boolean automata

    Leiss E. Succinct representation of regular languages by boolean automata. Theoretical Computer Science,

    work page

  29. [29]

    doi:10.1016/S0304-3975(81)80005-9

    13(3):323–330. doi:10.1016/S0304-3975(81)80005-9

    work page doi:10.1016/s0304-3975(81)80005-9

  30. [30]

    Descriptional complexity of NFA of different a mbiguity

    Leung H. Descriptional complexity of NFA of different a mbiguity. International Journal of F oundations of Computer Science , 2005. 16(5):975–984. doi:10.1142/S0129054105003418

    work page doi:10.1142/s0129054105003418 2005

  31. [31]

    Relating the type of ambiguity o f finite automata to the succinctness of their representation

    Ravikumar B, Ibarra OH. Relating the type of ambiguity o f finite automata to the succinctness of their representation. SIAM Journal of Computing , 1989. 18(6):1263–1282. doi:10.1137/0218083

    work page doi:10.1137/0218083 1989

  32. [32]

    Separating exponentially ambiguous finite aut omata from polynomially ambiguous finite au- tomata

    Leung H. Separating exponentially ambiguous finite aut omata from polynomially ambiguous finite au- tomata. SIAM Journal of Computing , 1998. 27(4):1073–1082. doi:10.1137/S0097539793252092

    work page doi:10.1137/s0097539793252092 1998

  33. [33]

    Communication complexity method for measuring nondeterminism in finite automata

    Hromkoviˇ c J, Seibert S, Karhum¨ aki J, Klauck H, Schnit ger G. Communication complexity method for measuring nondeterminism in finite automata. Information and Computation , 2002. 172(2):202–217. doi:10.1006/inco.2001.3069

    work page doi:10.1006/inco.2001.3069 2002

  34. [34]

    Ambiguity and communication

    Hromkoviˇ c J, Schnitger G. Ambiguity and communication. Theory of Computing Systems, 2011. 48:517–

    work page 2011

  35. [35]

    doi:10.1007/s00224-010-9277-4

    work page doi:10.1007/s00224-010-9277-4

  36. [36]

    On measuring nond eterminism in regular languages

    Goldstine J, Kintala CMR, Wotschke D. On measuring nond eterminism in regular languages. Information and Computation, 1990. 86(2):179–194. doi:10.1016/0890-5401(90)90053-K

    work page doi:10.1016/0890-5401(90)90053-k 1990

  37. [37]

    The tractability frontier forNFA minimization

    Bj¨ orklund H, Martens W . The tractability frontier forNFA minimization. Journal of Computer and System Sciences, 2012. 78(1):198–210. doi:10.1016/j.jcss.2011.03.001

    work page doi:10.1016/j.jcss.2011.03.001 2012

  38. [38]

    Ambiguity, nondeterminis m and state complexity of finite automata

    Han YS, Salomaa A, Salomaa K. Ambiguity, nondeterminis m and state complexity of finite automata. Acta Cybernetica, 2017. 23(1):141–157. doi:10.14232/actacyb.23.1.2017.9

    work page doi:10.14232/actacyb.23.1.2017.9 2017

  39. [39]

    State complexity of fin ite tree width NFAs

    Palioudakis A, Salomaa K, Akl SG. State complexity of fin ite tree width NFAs. Journal of Automata, Languages and Combinatorics , 2012. 17(2–4):245–264. doi:10.25596/jalc-2012-245

    work page doi:10.25596/jalc-2012-245 2012

  40. [40]

    State complexity of regular languages

    Y u S. State complexity of regular languages. Journal of Automata, Languages and Combinatorics , 2001. 6(2):221–234. doi:10.25596/jalc-2001-221

    work page doi:10.25596/jalc-2001-221 2001

  41. [41]

    Madhusudan

    Alur R, Madhusudan P . Visibly pushdown languages. In: P roceedings of STOC 2004. ACM, 2004 pp. 202–211. doi:10.1145/1007352.1007390

    work page doi:10.1145/1007352.1007390 2004

  42. [42]

    Complexity of input-driven pushd own automata

    Okhotin A, Salomaa K. Complexity of input-driven pushd own automata. ACM SIGACT News , 2014. 45(2):47–67. doi:10.1145/2636805.2636821

    work page doi:10.1145/2636805.2636821 2014

  43. [43]

    State complexity of combined op erations with two basic operations

    Cui B, Gao Y , Kari L, Y u S. State complexity of combined op erations with two basic operations. Theo- retical Computer Science, 2012. 437:82–102. doi:10.1016/j.tcs.2012.02.030

    work page doi:10.1016/j.tcs.2012.02.030 2012

  44. [44]

    Estimation of state complexity of combined operations

    ´Esik Z, Gao Y , Liu G, Y u S. Estimation of state complexity of combined operations. Theoretical Computer Science, 2009. 410(35):3272–3280. doi:10.1016/j.tcs.2009.03.026

    work page doi:10.1016/j.tcs.2009.03.026 2009

  45. [45]

    Undecidability of state comp lexity

    Salomaa A, Salomaa K, Y u S. Undecidability of state comp lexity. International Journal of Computer Mathematics, 2013. 90(6):1310–1320. doi:10.1080/00207160.2012.704994

    work page doi:10.1080/00207160.2012.704994 2013