Elements of the Theory of Computation

by Harry R. Lewis

Other authorsChristos H. Papadimitriou (Author)
Paperback, 1988

Status

Available

Call number

511.3

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 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)

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
Page: 0.2372 seconds