Analysis of blow-up situation in finite automata
Abstract
The blow-up phenomenon in finite automata is one of the most far reaching and significant problems in formal language theory and system design based on automata. Discovering a nondeterministic finite automaton (NFA) transformed into an equivalent deterministic finite automaton (DFA) with the famous powerset construction can lead to an exponentially larger number of states and this phenomenon is known as the state explosion, which makes solving even moderately sized input automata computationally infeasible. This issue is also known as the blow-up problem and has far reaching consequences on the compilation design, pattern matching engines, model checking systems, natural language processing pipelines, and network intrusion detection systems. The interaction between descriptional complexity and operational complexity with mitigating strategies despite decades of theoretical exploration has not been fully synthesized in the light of an emerging computational requirement. The review is a systematic literature review of articles published as early as 2019 and 2025 to identify the contemporary picture of the analysis of blow-ups in finite automata. The paper also determines the mathematical properties of exponential blowup; it discusses the effectiveness of modern heuristic and algebraic mitigation strategies. It has been shown in the analysis that the worst-case exponential lower bounds are tight in proving that classical NFA to DFA conversion is impossible, although in practice the improvements of up to 40-60% are possible by using state-aware lazy determinization and simulation-based reduction.
Full text article
References
[1] Straubing H. Finite automata, formal logic, and circuit complexity. Springer Science & Business Media; 2012 Dec 6.
[2] Meduna A, Zemek P. Jumping finite automata. International Journal of Foundations of Computer Science. 2012 Nov;23(07):1555-78. https://doi.org/10.1142/S0129054112500244
[3] Holzer M, Kutrib M. Descriptional and computational complexity of finite automata-A survey. Information and Computation. 2011 Mar 1;209(3):456-70. https://doi.org/10.1016/j.ic.2010.11.013
[4] Doyen L, Raskin JF. Antichain algorithms for finite automata. InInternational Conference on Tools and Algorithms for the Construction and Analysis of Systems 2010 Mar 20 (pp. 2-22). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-12002-2_2
[5] Büchi JR. Finite automata, their algebras and grammars: towards a theory of formal expressions. Springer Science & Business Media; 2013 Jun 29.
[6] Béal MP, Perrin D. Symbolic dynamics and finite automata. InHandbook of Formal Languages: Volume 2. Linear Modeling: Background and Application 2013 Mar 26 (pp. 463-506). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-07675-0_10
[7] De Giacomo G, Favorito M. Compositional approach to translate LTLf/LDLf into deterministic finite automata. InProceedings of the International Conference on Automated Planning and Scheduling 2021 May 17 (Vol. 31, pp. 122-130). https://doi.org/10.1609/icaps.v31i1.15954
[8] Khoussainov B, Nerode A. Automata theory and its applications. Springer Science & Business Media; 2012 Dec 6.
[9] Chatterjee S, De S, Samanta S, Ghosh A. Comparison Study and Operation Collapsing Issues for Serial Implementation of Square Matrix Multiplication Approach Suitable in High Performance Computing Environment. Available at SSRN 3722843. 2020 Apr 10.
[10] Li Y. Finite automata theory with membership values in lattices. Information Sciences. 2011 Mar 1;181(5):1003-17. https://doi.org/10.1016/j.ins.2010.11.006
[11] Xu X, Hong Y. Matrix expression and reachability analysis of finite automata. Journal of Control Theory and Applications. 2012 May;10(2):210-5. https://doi.org/10.1007/s11768-012-1178-4
[12] Droste M, Stüber T, Vogler H. Weighted finite automata over strong bimonoids. Information Sciences. 2010 Jan 2;180(1):156-66. https://doi.org/10.1016/j.ins.2009.09.003
[13] Blanton M, Aliasgari M. Secure outsourcing of DNA searching via finite automata. InIFIP Annual Conference on Data and Applications Security and Privacy 2010 Jun 21 (pp. 49-64). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-13739-6_4
[14] Saboori A, Hadjicostis CN. Current-state opacity formulations in probabilistic finite automata. IEEE Transactions on automatic control. 2013 Aug 28;59(1):120-33. https://doi.org/10.1109/TAC.2013.2279914
[15] Zhang K, Zhang L. Observability of Boolean control networks: A unified approach based on finite automata. IEEE Transactions on Automatic Control. 2015 Nov 18;61(9):2733-8. https://doi.org/10.1109/TAC.2015.2501365
[16] Ko BC, Ham SJ, Nam JY. Modeling and formalization of fuzzy finite automata for detection of irregular fire flames. IEEE Transactions on Circuits and Systems for Video Technology. 2011 May 19;21(12):1903-12. https://doi.org/10.1109/TCSVT.2011.2157190
[17] Linz P, Rodger SH. An introduction to formal languages and automata. Jones & Bartlett Learning; 2022 Feb 18.
[18] Yakaryilmaz A, Say AC. Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics & Theoretical Computer Science. 2010 Jan 1;12. https://doi.org/10.46298/dmtcs.509
[19] Prithi S, Sumathi S. LD2FA-PSO: A novel learning dynamic deterministic finite automata with PSO algorithm for secured energy efficient routing in wireless sensor network. Ad Hoc Networks. 2020 Feb 1;97:102024. https://doi.org/10.1016/j.adhoc.2019.102024
[20] Ouedraogo L, Kumar R, Malik R, Akesson K. Nonblocking and safe control of discrete-event systems modeled as extended finite automata. IEEE Transactions on Automation Science and Engineering. 2011 Apr 5;8(3):560-9. https://doi.org/10.1109/TASE.2011.2124457
[21] Grumberg O, Kupferman O, Sheinvald S. Variable automata over infinite alphabets. InInternational Conference on Language and Automata Theory and Applications 2010 May 24 (pp. 561-572). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-13089-2_47
Authors
Copyright (c) 2026 Siddhartha Chatterjee, Ritwika Ghosh, Aparijita Das, Jonti Deuri, Suman Biswas (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright (c) 2025 International Journal of Applied Resilience and Sustainability (IJARS) 
This work is licensed under a Creative Commons Attribution 4.0 International License.