No label defined (Q4725753)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3999299
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3999299 |
Statements
1986
0 references
Ackermann function
0 references
automata theory
0 references
computability
0 references
finite automata
0 references
infinite automata
0 references
Turing machines
0 references
logical networks
0 references
state reduction
0 references
regular sets
0 references
universal automata
0 references
recursive functions
0 references
undecidable problems
0 references
0.8401042819023132
0 references
0.8326355218887329
0 references
0.8326355218887329
0 references
This book is one in the ''Series in Computer Science (in China)''. In the book, the author provides a nice introduction to several important areas of automata theory and computability with emphasis on the basic concepts, results, and methods of finite automata and infinite automata (Turing machines). The first part (from chapter 1 to chapter 8) of the book is devoted to the theory of finite automata. The author provides an elegant and concise introduction to the theory of logical networks, state reduction, regular sets, linear finite automata, autonomous finite automata, state identification experiment, memorization and invertibility. The second part (from chapter 9 to chapter 13) on infinite automata introduces universal automata, Turing machines, recursive functions on words, undecidable problems and computation with bounded time and space resource. The author provides a very concise introduction into some fundamental but quite nontrival construction methods of recursive function theory and computability. In particular, the last chapter gives the author's results on the computational complexity of the well-known Ackermann's function. The book is nicely written. The author covers a broad range of material, and thus provides a good introduction to the field. The proofs are well presented, each chapter contains a set of exercises. Therefore, this book can serve as a textbook for a variety of undergraduate or graduate courses on the theory of automata.
0 references