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:
68Q05Models of computation (Turing machines, etc.)
03DxxComputability; recursion theory
68Q25Analysis of algorithms and problem complexity
68Q42Grammars and rewriting systems
68Q45Formal languages and automata
94A60Cryptography
03-00Reference works (mathematical logic)
03-01Textbooks (mathematical logic)
68-00Reference works (computer science)
68-01Textbooks (computer science)