Design of a recursive algorithm for DFA implementation: computational complexity analysis

Ashley Torres-Pérez; Eduardo Cornejo-Velázquez; Mireya Clavel-Maqueda

doi:10.61467/2007.1558.2026.v17i1.1172

Authors

Ashley Torres-Pérez Instituto de Ciencias Básicas e Ingeniería, Universidad Autónoma del Estado de Hidalgo https://orcid.org/0009-0004-3286-0993
Eduardo Cornejo-Velázquez Universidad Autónoma del Estado de Hidalgo https://orcid.org/0000-0002-0653-9459
Mireya Clavel-Maqueda Instituto de Ciencias Básicas e Ingenería, Universidad Autónoma del Estado de Hidalgo https://orcid.org/0000-0002-5487-9888

DOI:

https://doi.org/10.61467/2007.1558.2026.v17i1.1172

Keywords:

Computational Complexity, programming, deterministic finite automaton

Abstract

Computational complexity, in its practical application, quantifies the time and memory space required for an algorithm’s execution, thereby allowing the assessment of its efficiency and limitations with respect to input size. In this work, the design of a recursive algorithm for implementing a deterministic finite automaton (DFA) to recognise regular languages is presented. The divide-and-conquer technique was employed to select appropriate data structures and to define a recursive function for resolving the transition functions between states. The recursive algorithm was implemented in the C++ language and exhibits linear temporal and spatial computational complexity, which is intended to support different configurations for the evaluation of multiple input strings. The proposed algorithm is consistent with the theoretical definitions, and the computational complexity analysis provides support for its classification based on the input parameters.

Smart citations: https://scite.ai/reports/10.61467/2007.1558.2026.v17i1.1172
Dimensions.
Open Alex.

References

Blanc, M., & Bournez, O. (2024). The complexity of computing in continuous time: Space complexity is precision. arXiv. https://doi.org/10.48550/arXiv.2403.02499

Carl, M. (2019). Space and time complexity for infinite time Turing machines. Journal of Logic and Computation, 30, 1239–1255. https://doi.org/10.1093/logcom/exaa025

Cook, S. (1983). An overview of computational complexity. Communications of the ACM, 26, 400–408. https://doi.org/10.1145/358141.358144

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.

Dean, W. (2019). Computational complexity theory and the philosophy of mathematics. Philosophia Mathematica. https://doi.org/10.1093/philmat/nkz021

Dean, W. (2021). Computational complexity theory. In E. N. Zalta (Ed.), The Stanford Encyclopedia of Philosophy (Fall 2021 ed.). https://plato.stanford.edu/archives/fall2021/entries/computational-complexity/

Fortnow, L., & Homer, S. (2014). Computational complexity. In Handbook of the History of Logic (Vol. 9, pp. 495–521). North-Holland.

GeeksforGeeks. (2024). unordered_map::find() in C++ STL. https://www.geeksforgeeks.org/unordered-mapfind-in-c-stl/

Gnatenko, A., Kutz, O., & Troquard, N. (2024). Building an ontology of computational complexity. In Proceedings of the Joint Ontology Workshops (JOWO) – Episode X (FOIS 2024). CEUR-WS. https://ceur-ws.org/Vol-3882/foust-9.pdf

Hashimoto, K., Iizuka, N., & Sugishita, S. (2017). Time evolution of complexity in Abelian gauge theories. Physical Review D, 96, 126001. https://doi.org/10.1103/PhysRevD.96.126001

Karp, R. M. (2021). Reducibility among combinatorial problems. In H. R. Lewis (Ed.), Ideas that created the future: Classic papers of computer science (pp. 141–156). MIT Press. https://doi.org/10.7551/mitpress/12274.003.0038

Koshy, T. (2004). Discrete mathematics with applications. Elsevier Science & Technology.

Kozen, D. C. (1997). Automata and computability. Springer.

Latkin, I. (2023). A correspondence between the time and space complexity. arXiv. https://doi.org/10.48550/arXiv.2311.01184

Mohan, N. (2019). Understanding time and space complexity in algorithms. International Journal of Science and Research (IJSR). https://doi.org/10.21275/sr24923134130

OmegaUp. (2025). 15320. Simulación de un autómata finito determinista. https://omegaup.com/arena/problem/Simulacion-de-DFA/

Schertzer, D., & Lovejoy, S. (2004). Space–time complexity and multifractal predictability. Physica A: Statistical Mechanics and Its Applications, 338, 173–186. https://doi.org/10.1016/j.physa.2004.04.032

Sipser, M. (2006). Introduction to the theory of computation (2nd ed.). MIT Press.

Zhang, N. (2022). 50 years of computational complexity: Hao Wang and the theory of computation. arXiv. https://doi.org/10.48550/arXiv.2206.05274

Design of a recursive algorithm for DFA implementation: computational complexity analysis

Authors

DOI:

Keywords:

Abstract

References

Downloads

Published

How to Cite

Issue

Section

License

Most read articles by the same author(s)

Information

Current Issue