This abstract machine can be in exactly one of a finite number of states at any given time. It is a mathematical model of computation. It possesses a set of states and rules that are used for moving from one state to another, but it is dependent on the applied input symbol.Įssentially, it is pretty much an abstract model of a digital computer. It is an abstract machine that has five elements or tuples. Leiss, E.Finite automata or finite state machine is the simplest machine that is used for recognizing patterns. Leiss, E.: Succinct representation of regular languages by Boolean automata. Lange, K.J., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Foundations of Computer Science (FOCS 1977), pp. Kozen, D.: Lower bounds for natural proof systems. Jones, N.: Space-bounded reducibility among combinatorial problems. Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over a unary alphabet. Immerman, N.: Nondeterministic space is closed under complementation. Ibarra, O.H., Ravikumar, B.: On sparseness, ambiguity and other decision problems for acceptors and transducers. In: Informatik, Festschrift zum 60, Geburtstag von Günter Hotz, Teubner, pp. Huynh, D.T.: Complexity of closeness, sparseness and segment equivalence for context-free and regular languages. Hunt III, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. Hunt III, H.B., Rosenkrantz, D.J.: Computational parallels between the regular and context-free languages. Hunt III, H.B., Rosenkrantz, D.J.: On equivalence and contaiment problems for formal languages. Hunt III, H.B.: Observations on the complexity of regular expressions problems. In: Symposium on Theory of Computing (STOC 1973), pp. Hunt III, H.B.: On the time and tape complexity of languages I. thesis, Cornell University, Ithaca, New York, USA (1973) Hunt III, H.B.: On the time and tape complexity of languages. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. In: The Theory of Machines and Computations, pp. Hopcroft, J.: An nlog n algorithm for minimizing the state in a finite automaton. Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. Holzer, M., Kutrib, M.: Nondeterministic finite automata-recent results on the descriptional and computational complexity. Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Developments in Language Theory II at the Crossroads of Mathematics, Computer Science and Biology, pp. Holzer, M.: On emptiness and counting for alternating finite automata. Hartmanis, J., Hunt III, H.B.: The LBA problem and its importance in the theory of computing. In: Harju, T., Karhumäki, J., Lepistö, A. Logic 24, 1–48 (1983)Īnderson, T., Rampersad, N., Santean, N., Shallit, J., Loftus, J.: Detecting palindroms, patterns and borders in regular languages (2008) arXiv:0711.3183v2 īarrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. Álvarez, C., Jenner, B.: A very hard log-space counting class. This process is experimental and the keywords may be updated as the learning algorithm improves.Īho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. These keywords were added by machine and not by the authors. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

We thus come across descriptional and computational complexity issues of finite automata. 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. In the present paper, we tour a fragment of this literature. 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.

Finite automaton