EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Analysis of blow-up situation in finite automata

Siddhartha Chatterjee, Ritwika Ghosh, Aparijita Das, Jonti Deuri, Suman Biswas

International Journal of Applied Resilience and Sustainability · 04.03.2026 · 2 (2) · 599-617

DOI: 10.70593/deepsci.0202023 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Applied Resilience and Sustainability, online erschienen am 04.03.2026. Verfasst von Siddhartha Chatterjee und 4 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Chatterjee, S., Ghosh, R., Das, A., Deuri, J., & Biswas, S. (2026). Analysis of blow-up situation in finite automata. International Journal of Applied Resilience and Sustainability, 2(2), 599-617. https://doi.org/10.70593/deepsci.0202023

Vancouver

Chatterjee S, Ghosh R, Das A, Deuri J, Biswas S. Analysis of blow-up situation in finite automata. International Journal of Applied Resilience and Sustainability. 2026;2(2):599-617. doi:10.70593/deepsci.0202023

BibTeX
@article{Chatterjee2026,
  author = {Chatterjee, Siddhartha and Ghosh, Ritwika and Das, Aparijita and Deuri, Jonti and Biswas, Suman},
  title = {Analysis of blow-up situation in finite automata},
  journal = {International Journal of Applied Resilience and Sustainability},
  year = {2026},
  volume = {2},
  number = {2},
  pages = {599--617},
  doi = {10.70593/deepsci.0202023}
}
Kostenlos starten →