Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today's computational theory course, this revision continues the book's well-know, approachable style with timely revisions, additional practice, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E's comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.

lgrsnf/Sipser, Michael (2013).pdf

Sipser, Michael

CENGAGE Learning Custom Publishing

Cengage Learning EMEA (UK & Europe), [N.p.], 2012

3rd ed., Boston, MA, Massachusetts, 2013

United States, United States of America

Third edition, Boston, MA, 2013

3rd ed, Australia, 2013

3, 2012

Includes bibliographical references (p. 443-447) and index.

MiU

Cover
Statement
Title Page
Copyright
Dedication
Contents
Preface to the First Edition
Preface to the Second Edition
Preface to the Third Edition
Ch 0: Introduction
0.1 Automata, Computability, and Complexity
0.2 Mathematical Notions and Terminology
0.3 Definitions, Theorems, and Proofs
0.4 Types of Proof
Exercises
Problems
Selected Solutions
Part 1: Automata and Languages
Ch 1: Regular Languages
Introduction
1.1 Finite Automata
1.2 Nondeterminism
1.3 Regular Expressions
1.4 Nonregular Languages
Exercises
Problems
Selected Solutions
Ch 2: Context-Free Languages
Introduction
2.1 Context-Free Grammars
2.2 Pushdown Automata
2.3 Non-Context-Free Languages
2.4 Deterministic Context-Free Languages
Exercises
Problems
Selected Solutions
Part 2: Computability Theory
Ch 3: The Church–Turing Thesis
Introduction
3.1 Turing Machines
3.2 Variants of Turing Machines
3.3 The Definition of Algorithm
Exercises
Problems
Selected Solutions
Ch 4: Decidability
Introduction
4.1 Decidable Languages
4.2 Undecidability
Exercises
Problems
Selected Solutions
Ch 5: Reducibility
Introduction
5.1 Undecidable Problems From Language Theory
5.2 A Simple Undecidable Problem
5.3 Mapping Reducibility
Exercises
Problems
Selected Solutions
Ch 6: Advanced Topics in Computability Theory
Introduction
6.1 The Recursion Theorem
6.2 Decidability of logical theories
6.3 Turing Reducibility
6.4 A Definition of Information
Exercises
Problems
Selected Solutions
Part 3: Complexity Theory
Ch 7: Time Complexity
Introduction
7.1 Measuring Complexity
7.2 The Class P
7.3 The Class NP
7.4 NP-completeness
7.5 Additional NP-complete Problems
Exercises
Problems
Selected Solutions
Ch 8: Space Complexity
Introduction
8.1 Savitch’s Theorem
8.2 The Class PSPACE
8.3 PSPACE-completeness
8.4 The Classes L and NL
8.5 NL-completeness
8.6 NL equals coNL
Exercises
Problems
Selected Solutions
Ch 9: Intractability
Introduction
9.1 Hierarchy Theorems
9.2 Relativization
9.3 Circuit Complexity
Exercises
Problems
Selected Solutions
Ch 10: Advanced Topics in Complexity Theory
Introduction
10.1 Approximation Algorithms
10.2 Probabilistic Algorithms
10.3 Alternation
10.4 Interactive Proof Systems
10.5 Parallel Computation
10.6 Cryptography
Exercises
Problems
Selected Solutions
Selected Bibliography
Index

The number one choice for today's computational theory course, this highly anticipated revision retains the unmatched clarity and thorough coverage that make it a leading text for upper-level undergraduate and introductory graduate students. This edition continues author Michael Sipser's well-known, approachable style with timely revisions, additional exercises, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. This edition's refined presentation ensures a trusted accuracy and clarity that make the challenging study of computational theory accessible and intuitive to students while maintaining the subject's rigor and formalism. Readers gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs

Part 1: Automata And Languages. 1. Regular Languages ; 2. Context-free Languages -- Part 2: Computability Theory. 3. The Church-turing Thesis ; 4. Decidability ; 5. Reducibility ; 6. Advanced Topics In Computability Theory -- Part 3: Complexity Theory. 7. Time Complexity ; 8. Space Complexity ; 9. Interactibility ; 10. Advanced Topics In Complexity Theory. Michael Sipser. Includes Bibliographical References (pages 443-447) And Index.

"Gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. This books comprehensive coverage makes it a valuable reference for studies in theoretical computing."-- Provided by publisher

2024-02-01