Additional Reading

Daniel I.A. Cohen,Introduction to Computer Theory, rev. ed. (1991), provides an introduction to automata, formal languages, and Turing machines at the undergraduate level.J.E. Pin,Varieties of Formal Languages, rev. and updated ed. (1986; originally published in French, 1984), introduces the theory of finite automata and regular languages. A readable introduction to automata theory as a formal theory of systems isM.W. Shields,An Introduction to Automata Theory (1987).Marvin L. Minsky,Computation: Finite and Infinite Machines (1967); andR.J. Nelson,Introduction to Automata (1967), are comprehensive elementary introductions to automata theory.Michael A. Arbib,Theories of Abstract Automata (1969); andBoleslaw Mikolajczak (ed.),Algebraic and Structural Automata Theory (1991; originally published in Polish, 1985), are more advanced introductions.Jiří Adámek andVěra Trnková,Automata and Algebras in Categories (1990), develops automata theory and category theory together.Samuel Eilenberg,Automata, Languages, and Machines, 2 vol. (1974–76), provides a centralized presentation of important topics in automata theory and formal language theory.Martin Davis,Computability & Unsolvability (1958);H. Rogers,Theory of Recursive Functions and Effective Computability (1967, reissued 1987);George S. Boolos andRichard C. Jeffrey,Computability and Logic, 3rd ed. (1989);J. Glenn Brookshear,Theory of Computation: Formal Languages, Automata, and Complexity (1989); andRobert I. Soare,Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (1987), are concerned with the concepts of Turing computability and the theory of recursive functions.

C.E. Shannon andJ. McCarthy (eds.),Automata Studies (1956), contains some of the original basic material concerning neural nets and automata with unreliable components or with random elements.Michael Chester,Neural Networks: A Tutorial (1993), is an elementary introduction and survey.Françoise Fogelman Soulié,Yves Robert, andMaurice Tchuente (eds.),Automata Networks in Computer Science (1987), introduces automata networks and gives applications.Eric Goles andServet Martínez,Neural and Automata Networks (1990), focuses on dynamical neural networks and reviews important results with applications to statistical physics.

Pál Ruján, “Cellular Automata and Statistical Mechanical Models,”Journal of Statistical Physics, 49(1–2):139–222 (1987), introduces cellular automata in connection with lattice models.Kumpati S. Narendra andMandayam A.L. Thathachar,Learning Automata (1989), is a technical introduction.Norbert Wieneret al., Differential Space, Quantum Systems, and Prediction (1966), discusses the automaton and its environment in the sense of prediction theory and gives reference to other literature in this area as well as the area of computable probability spaces. Good accounts of automata theory and its relations to switching theory areMichael A. Harrison,Introduction to Switching and Automata Theory (1965); andS.T. Hu,Mathematical Theory of Switching Circuits and Automata (1968). A good introduction to machine decomposition theory isJ. Hartmanis andR.E. Stearns,Algebraic Structure Theory of Sequential Machines (1966).Noam Chomsky, “Formal Properties of Grammars,” inR. Duncan Luce,Robert R. Bush, andEugene Galanter (eds.),Handbook of Mathematical Psychology, vol. 2 (1963), pp. 323–418, is a well-respected survey of the field of automata and generative grammars. Articles presenting approaches to languages and automata from very general mathematical points of view areSeymour Ginsburg andSheilah Greibach, “Abstract Families of Languages,”Memoirs of the American Mathematical Society, 87:1–32 (1969); andGene F. Rose, “Abstract Families of Processors,”Journal of Computer and System Sciences, 4:193–204 (1970).J. Richard Büchi,Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions (1989), presents a centralized discussion of automata theory considering automata as algebras.

Article Contributors

Primary Contributors

• R.J. Nelson
• Bayard Rankin
• The Editors of Encyclopaedia Britannica
  Encyclopaedia Britannica's editors oversee subject areas in which they have extensive knowledge, whether from years of experience gained by working on that content or via study for an advanced degree. They write new content and verify and edit content received from contributors.

Other Encyclopedia Britannica Contributors

• Aakanksha Gaur
• Gloria Lotha
• Emily Rodriguez

Article History