Harry R. Lewis

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 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.… (more)