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  is generated by a -automaton iff the formal power series with coefficients  is algebraic on the field of rational elements , where  and  are polynomials with coefficients in the finite field .

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.