TOPICS
Search

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, Cellular Automaton, Turing Machine

Explore with Wolfram|Alpha

References

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. https://mathworld.wolfram.com/AutomataTheory.html

Subject classifications