# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Computation and automata. (English) Zbl 0565.68046
Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge etc.: Cambridge University Press. XIII, 282 p. £25.00; \$ 39.50 (1985).
The monograph gives an introduction to certain central topics in theoretical computer science and presents the material in a clear and mathematical perspective. Each section is developed from the beginning and quickly proceeds to the more advanced contents. Proofs usually are concise and some of them are skipped or replaced by scarce references. This book is an exposition of an important part of areas dealing with mathematical foundations of computer science, not including correctness of programs, data structures, data bases, and semantics. A central role is occupied by the classical computability theory initiated by the work of Gödel, Tarski, Church, Thue, Post, Turing, and Kleene. The recursively enumerable sets are defined through phrase structure grammars using semi-Thue like rewriting systems. As equivalents to those are identified: Post canonical systems, Markov algorithms, and Turing machines. In the proofs tedious constructions with a formal machine model are avoided. Automata, not only GSM’s and Turing machines, are formally defined by certain rewriting (i.e., semi-Thue) systems. The recursive function theory includes, among others, the ${S}_{m,n}$-theorem, recursion-theorem, and discusses degrees of undecidability, creative and productive sets. The chapter on computational complexity contains axiomatic as well as machine oriented complexity theory. The undecidability results, as usual, are based on the halting problem and the therefrom derived PCP. The famous Hilbert’s tenth problem is included as well as a section on cryptography. As modern trends are shortly discussed: Petri nets, grammar forms, and systolic automata. Every chapter closes with exercises, and their titles (number of pages) are: Introduction: Models of Computation (4), Rudiments of Language Theory (36), Restricted Automata (29), Turing Machines and Recursive Functions (38), Famous Decision Problems (20), Computational Complexity (45), Cryptography (43), Trends in Automata and Language Theory (9). The book, dedicated to the advanced undergraduate is appropriate for the graduate as well.
Reviewer: M.Jantzen

##### MSC:
 68Q05 Models of computation (Turing machines, etc.) 03Dxx Computability; recursion theory 68Q25 Analysis of algorithms and problem complexity 68Q42 Grammars and rewriting systems 68Q45 Formal languages and automata 94A60 Cryptography 03-00 Reference works (mathematical logic) 03-01 Textbooks (mathematical logic) 68-00 Reference works (computer science) 68-01 Textbooks (computer science)