Abstract
Over the last half century, a vast literature documenting the importance of deterministic, nondeterministic, and alternating finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss developments relevant to finite automata related problems like, for example, (i) simulation of and by several types of finite automata, (ii) standard automata problems such as, e.g., fixed and general membership, emptiness, universality, equivalence, and related problems, and (iii) minimization and approximation. We thus come across descriptional and computational complexity issues of finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addision-Wesley, Reading (1974)
Álvarez, C., Jenner, B.: A very hard log-space counting class. Theoret. Comput. Sci. 107, 3–30 (1993)
Ajtai, M.: \(\Sigma_1^1\) formulae on finite structures. Ann. Pure. Appl. Logic 24, 1–48 (1983)
Anderson, T., Rampersad, N., Santean, N., Shallit, J., Loftus, J.: Detecting palindroms, patterns and borders in regular languages (2008) arXiv:0711.3183v2 [cs.CC]
Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci. 38, 150–164 (1989)
Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within \(\mbox{NC}^1\). J. Comput. System Sci. 41, 274–306 (1990)
Barrington, D.M., Thérien, D.: Finite monoids and the fine structure of \(\mbox{NC}^1\). J. ACM 35, 941–952 (1988)
Björklund, H., Martens, W.: The tractability frontier for NFA minimization. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 27–38. Springer, Heidelberg (2008)
Brzozowski, J.A., Leiss, E.L.: On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10, 19–35 (1980)
Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. J. ACM 21, 114–133 (1981)
Cho, S., Huynh, D.T.: Finite-automaton aperiodicity is PSPACE-complete. Theoret. Comput. Sci. 88, 99–116 (1991)
Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inform. Comput. 97, 1–22 (1992)
Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47, 149–158 (1986)
Chrobak, M.: Errata to finite automata and unary languages. Theoret. Comput. Sci. 302, 497–498 (2003)
Cohen, R.S., Brzozowski, J.A.: Dot-depth of star-free events. J. Comput. System Sci. 5, 1–16 (1971)
Eilenberg, S.: Automata, Languages, and Machines (Volume B), vol. 59-B. Academic Press, London (1976)
Fellah, A., Jürgensen, H., Yu, S.: Constructions for alternating finite automata. Internat. J. Comput. Math. 35, 117–132 (1990)
Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory 17, 13–27 (1984)
Galil, Z.: Hierarchies of complete problems. Acta Inform. 6, 77–88 (1976)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gold, E.M.: Complexity of automaton identification from given data. Inform. Control 37, 302–320 (1978)
Gramlich, G.: Probabilistic and nondeterministic unary automata. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 460–469. Springer, Heidelberg (2003)
Gramlich, G., Schnitger, G.: Minimizing nFA’s and regular expressions. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 399–411. Springer, Heidelberg (2005)
Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 363–374. Springer, Heidelberg (2006)
Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: Language and Automata Theory and Applications (LATA 2007), pp. 261–272. Technical Report 35/07, Universitat Rovira i Virgili, Tarragona (2007)
Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming \(\mbox{P}\neq\mbox{NP}\). In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 205–216. Springer, Heidelberg (2007)
Hartmanis, J., Hunt III, H.B.: The LBA problem and its importance in the theory of computing. In: SIAM AMS. Complexity of Computing, vol. 7, pp. 1–26 (1974)
Holzer, M.: On emptiness and counting for alternating finite automata. In: Developments in Language Theory II; at the Crossroads of Mathematics, Computer Science and Biology, pp. 88–97. World Scientific, Singapore (1996)
Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148–157. Springer, Heidelberg (2003)
Holzer, M., Kutrib, M.: Nondeterministic finite automata—recent results on the descriptional and computational complexity. In: Ibarra, O., Ravikumar, B. (eds.) CIAA 2008. LNCS, vol. 5148, pp. 1–16. Springer, Heidelberg (2008)
Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Autom., Lang. Comb. 6, 453–466 (2001)
Hopcroft, J.: An nlogn algorithm for minimizing the state in a finite automaton. In: The Theory of Machines and Computations, pp. 189–196. Academic Press, London (1971)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)
Hunt III, H.B.: On the time and tape complexity of languages. Ph.D. thesis, Cornell University, Ithaca, New York, USA (1973)
Hunt III, H.B.: On the time and tape complexity of languages I. In: Symposium on Theory of Computing (STOC 1973), pp. 10–19. ACM Press, New York (1973)
Hunt III, H.B.: Observations on the complexity of regular expressions problems. J. Comput. System Sci. 19, 222–236 (1979)
Hunt III, H.B., Rosenkrantz, D.J.: On equivalence and contaiment problems for formal languages. J. ACM 24, 387–396 (1977)
Hunt III, H.B., Rosenkrantz, D.J.: Computational parallels between the regular and context-free languages. SIAM J. Comput. 7, 99–114 (1978)
Hunt III, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. System Sci. 12, 222–268 (1976)
Huynh, D.T.: Complexity of closeness, sparseness and segment equivalence for context-free and regular languages. In: Informatik, Festschrift zum 60, Geburtstag von Günter Hotz, Teubner, pp. 235–251 (1992)
Ibarra, O.H., Ravikumar, B.: On sparseness, ambiguity and other decision problems for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol. 210, pp. 171–179. Springer, Heidelberg (1985)
Ilie, L., Yu, S.: Follow automata. Inform. Comput. 186, 140–162 (2003)
Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17, 935–938 (1988)
Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over a unary alphabet. Internat. J. Found. Comput. Sci. 2, 163–182 (1991)
Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Inform. Process. Lett. 40, 25–31 (1991)
Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22, 1117–1141 (1993)
Jones, N.: Space-bounded reducibility among combinatorial problems. J. Comput. System Sci. 11, 68–85 (1975)
Kozen, D.: Lower bounds for natural proof systems. In: Foundations of Computer Science (FOCS 1977), pp. 254–266. IEEE Society Press, Los Alamitos (1977)
Lange, K.J., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 346–354. Springer, Heidelberg (1992)
Leiss, E.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)
Leiss, E.: Succinct representation of regular languages by Boolean automata. II. Theoret. Comput. Sci. 38, 133–136 (1985)
Malcher, A.: Minimizing finite automata is computationally hard. Theoret. Comput. Sci. 327, 375–390 (2004)
McKenzie, P., Péladeau, P., Thérien, D.: \(\mbox{NC}^1\): The automata-theoretical viewpoint. Comput. Compl. 1, 330–359 (1991)
McNaughton, R., Papert, S.: Counter-free automata. Research monographs, vol. 65. MIT Press, Cambridge (1971)
Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30, 1976–1992 (2001)
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: IEEE Symposium on Switching and Automata Theory (SWAT 1971), pp. 188–191. IEEE Society Press, Los Alamitos (1971)
Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Symposium on Switching and Automata Theory (SWAT 1972), pp. 125–129. IEEE Society Press, Los Alamitos (1972)
Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20, 1211–1214 (1971)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125 (1959)
Schützenberger, M.P.: On finite monoids having only trivial subgroups. Inform. Control 8, 190–194 (1965)
Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. System Sci. 21, 195–202 (1980)
Stearns, R.E., Hunt, H.B.: On the equivalence and containment problems for unambiguous regular expressions, regular grammars, and finite automata. SIAM J. Comput. 14, 598–611 (1985)
Stern, J.: Complexity of some problems from the theory of automata. Inform. Control 66, 163–176 (1985)
Stockmeyer, L.J.: The Complexity of Decision Problems in Automata Theory and Logic. Ph.D. thesis, MIT, Cambridge, Massasuchets, USA (1974)
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Symposium on Theory of Computing (STOC 1973), pp. 1–9. ACM Press, New York (1973)
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform. 26, 279–284 (1988)
Thérien, D.: Classification of finite monoids: the language approach. Theoret. Comput. Sci. 14, 195–208 (1981)
Yu, S.: State complexity of regular languages. J. Autom., Lang. Comb. 6, 221–234 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holzer, M., Kutrib, M. (2009). Descriptional and Computational Complexity of Finite Automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-00982-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00981-5
Online ISBN: 978-3-642-00982-2
eBook Packages: Computer ScienceComputer Science (R0)