Status
Available
Call number
Library's review
Indeholder "Preface", "Chapter 1. Sets, Relations and Languages", " 1.1 "If-Then" and its Relatives", " 1.2 Sets", " 1.3 Relations and Functions", " 1.4 Special Types of Binary Relations", " 1.5 Closures", " 1.6 Finite and Infinite Sets", " 1.7 Three Fundamental Proof Techniques", " 1.8 Alphabets
Udmærket standardlærebog i beregnelighedsteori.
Show More
and Languages", " 1.9 Finite Representation of Languages", " Problems", " References", "Chapter 2. Finite Automata", " 2.1 Deterministic Finite Automata", " 2.2 Nondeterministic Finite Automata", " 2.3 Equivalence of Deterministic and Nondeterministic Finite Automata", " 2.4 Properties of the Languages Accepted by Finite Automata", " 2.5 Finite Automata and Regular Expressions", " 2.6 Proofs that Languages Are and Are Not Regular", " Problems", " References", "Chapter 3. Context-Free Languages", " 3.1 Context-Free Grammars", " 3.2 Regular Languages and Context-Free Grammars", " 3.3 Pushdown Automata", " 3.4 Pushdown Automata and Context-Free Grammars", " 3.5 Properties of Context-Free Languages", " 3.5.1 Closure Properties", " 3.5.2 Periodicity Properties", " 3.5.3 Algorithmic Properties", " 3.6 Determinism and Parsing", " 3.6.1 Deterministic Pushdown Automata and Context-Free Languages", " 3.6.2 Top-Down Parsing", " 3.6.3 Bottom-Up Parsing", " Problems", " References", "Chapter 4. Turing Machines", " 4.1 The Definition of a Turing Machine", " 4.2 Computing with Turing Machines", " 4.3 Combining Turing Machines", " 4.4 Some Examples of More Powerful Turing Machines", " 4.5 Extensions of the Turing Machine", " 4.6 Nondeterministic Turing Machines", " Problems", " References", "Chapter 5. Church's Thesis", " 5.1 Church's Thesis", " 5.2 Grammars", " 5.3 The Primitive Recursive Functions", " 5.4 Gödelization", " 5.5 The μ-Recursive Functions", " 5.6 Turing-Computability of the μ-Recursive Functions", " 5.7 Universal Turing Machines", " Problems", " References", "Chapter 6. Uncomputability", " 6.1 The Halting Problem", " 6.2 Turing-Enumerability, Turing-Acceptability, and Turing-Decidability", " 6.3 Unsolvable Problems About Turing Machines and μ-Recursive Functions", " 6.4 Unsolvable Problems About Grammars and Similar Systems", " 6.4.1 Unsolvable Problems About Unrestricted Grammars", " 6.4.2 Thue Systems", " 6.4.3 Post's Correspondence Problem", " 6.4.4 Unsolvable Problems About Context-Free Grammars", " 6.5 An Unsolvable Tiling Problem", " Problems", " References", "Chapter 7. Computational Complexity", " 7.1 Time-Bounded Turing Machines", " 7.2 Rate of Growth of Functions", " 7.3 Time-Bounded Simulations", " 7.4 The Classes P and NP", " 7.5 NP-Completeness", " 7.6 Some NP-Complete Problems", " 7.6.1 A Bounded Tiling Problem", " 7.6.2 Integer Programming", " 7.6.3 The Travelling Salesman Problem", " 7.7 The Complexity Hierarchy", " Problems", " References", "Chapter 8. The Propositional Calculus", " 8.1 Introduction", " 8.2 Syntax of the Propositional Calculus", " 8.3 Truth-Assignments", " 8.4 Validity and Satisfiability", " 8.5 Equivalence and Normal Forms", " 8.6 Compactness", " 8.7 Resolution in the Propositional Calculus", " Problems", "Chapter 9. The Predicate Calculus", " 9.1 The Predicate Calculus: Syntax", " 9.2 Structures and Satisfiability", " 9.3 Equivalence", " 9.4 The Expansion Theorem", " 9.5 Three Applications of the Expansion Theorem", " 9.6 Unsolvability and NP-Completeness", " 9.7 Resolution in the Predicate Calculus", " Problems", " References", "Index".Udmærket standardlærebog i beregnelighedsteori.
Show Less
Publication
Pearson US Imports & Prentice Hall International (1988), Paperback, 466 pages
Description
Appropriate for senior and graduate level courses in Computer Science Theory, Automata, and Theory of Computation. This is the long awaited Second Edition of Lewis and Papadimitriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience.
Language
Original language
English
Physical description
466 p.; 22.8 cm
ISBN
0132734265 / 9780132734264
Local notes
Omslag: Ikke angivet
Omslaget viser titel og forfatternavne sat med hvid på rød baggrund
Indskannet omslag - N650U - 150 dpi
Omslaget viser titel og forfatternavne sat med hvid på rød baggrund
Indskannet omslag - N650U - 150 dpi
Similar in this library
Pages
466
DDC/MDS
| 511.3 |