Automata Theory

The mathematical study of abstract computing machines (especially Turing machines) and the analysis of algorithms used by such machines.

A connection between automata theory and number theory was provided by Christol et al. (1980), who showed that a sequence {a_n} is generated by a p-automaton iff the formal power series with coefficients a_n is algebraic on the field of rational elements A(X)/Q(X), where A(X) and Q(X) are polynomials with coefficients in the finite field F_p.

See also

Abstract Machine, Automatic Sequence, Cellular Automaton, Finite Automaton, Turing Machine

Explore with Wolfram|Alpha


Christol, G.; Kamae, T.; Mendès-France, M.; and Rauzy, G. "Suites Algébriques, automates et substitutions." Bull. Soc. Math. France 108, 401-419, 1980.Harrison, M. A. Introduction to Switching and Automata Theory. New York: McGraw-Hill, p. 188, 1965.Simon, M. Automata Theory. Singapore: World Scientific, 1999.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002.

Referenced on Wolfram|Alpha

Automata Theory

Cite this as:

Weisstein, Eric W. "Automata Theory." From MathWorld--A Wolfram Web Resource.

Subject classifications