Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0565.68046
Salomaa, Arto
Computation and automata. (English)
[B] Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge etc.: Cambridge University Press. XIII, 282 p. \sterling 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\sb{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.
[M.Jantzen]

MSC 2000:: *68Q05 Models of computation
03Dxx Recursion theory
68Q25 Analysis of algorithms and problem complexity
68Q42 Rewriting systems
68Q45 Formal languages
94A60 Cryptography
03-00 Reference works (mathematical logic)
03-01 Textbooks (mathematical logic)
68-00 Reference works (computer science)
68-01 Textbooks (computer science)

Keywords: semi-Thue systems; computability theory; recursively enumerable sets; phrase structure grammars; rewriting systems; Post canonical systems; Markov algorithms; Turing machines; recursive function theory; degrees of undecidability; computational complexity; halting problem; Hilbert's tenth problem; cryptography; Petri nets; grammar forms; systolic automata

Cited in: Zbl 1214.68163 Zbl 0728.68074 Zbl 0579.68037

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]