Amazon cover image
Image from Amazon.com

Introduction to the theory of computation / Michael Sipser.

By: Material type: TextTextLanguage: Publication details: Boston : Cengage Learning, 2006. 2013.Edition: 3rd edDescription: xix, 431 p. : ill. ; 25 cmISBN:
  • 9788131525296 (pbk.)
Subject(s): DDC classification:
  • 511.35 SIP
Contents:
Machine generated contents note: 0.Introduction 0.1.Automata, Computability, and Complexity Complexity theory Computability theory Automata theory 0.2.Mathematical Notions and Terminology Sets Sequences and tuples Functions and relations Graphs Strings and languages Boolean logic Summary of mathematical terms 0.3.Definitions, Theorems, and Proofs Finding proofs 0.4.Types of Proof Proof by construction Proof by contradiction Proof by induction Exercises, Problems, and Solutions pt. One Automata and Languages 1.Regular Languages 1.1.Finite Automata Formal definition of a finite automaton Examples of finite automata Formal definition of computation Designing finite automata The regular operations 1.2.Nondeterminism Formal definition of a nondeterministic finite automaton Equivalence of NFAs and DFAs Closure under the regular operations 1.3.Regular Expressions Contents note continued: Formal definition of a regular expression Equivalence with finite automata 1.4.Nonregular Languages The pumping lemma for regular languages 2.Context-Free Languages 2.1.Context-Free Grammars Formal definition of a context-free grammar Examples of context-free grammars Designing context-free grammars Ambiguity Chomsky normal form 2.2.Pushdown Automata Formal definition of a pushdown automaton Examples of pushdown automata Equivalence with context-free grammars 2.3.Non-Context-Free Languages The pumping lemma for context-free languages 2.4.Deterministic Context-Free Languages Properties of DCFLs Deterministic context-free grammars Relationship of DPDAs and DCFGs Parsing and LR(k) Grammars pt. Two Computability Theory 3.The Church-Turing Thesis 3.1.Turing Machines Formal definition of a Turing machine Contents note continued: Examples of Turing machines 3.2.Variants of Turing Machines Multitape Turing machines Nondeterministic Turing machines Enumerators Equivalence with other models 3.3.The Definition of Algorithm Hilbert's problems Terminology for describing Turing machines 4.Decidability 4.1.Decidable Languages Decidable problems concerning regular languages Decidable problems concerning context-free languages 4.2.Undecidability The diagonalization method An undecidable language A Turing-unrecognizable language 5.Reducibility 5.1.Undecidable Problems from Language Theory Reductions via computation histories 5.2.A Simple Undecidable Problem 5.3.Mapping Reducibility Computable functions Formal definition of mapping reducibility 6.Advanced Topics in Computability Theory Contents note continued: 6.1.The Recursion Theorem Self-reference Terminology for the recursion theorem Applications 6.2.Decidability of logical theories A decidable theory An undecidable theory 6.3.Turing Reducibility 6.4.A Definition of Information Minimal length descriptions Optimality of the definition Incompressible strings and randomness pt. Three Complexity Theory 7.Time Complexity 7.1.Measuring Complexity Big-O and small-o notation Analyzing algorithms Complexity relationships among models 7.2.The Class P Polynomial time Examples of problems in P 7.3.The Class NP Examples of problems in NP The P versus NP question 7.4.NP-completeness Polynomial time reducibility Definition of NP-completeness The Cook-Levin Theorem 7.5.Additional NP-complete Problems The vertex cover problem The Hamiltonian path problem The subset sum problem Contents note continued: Exercises, Problems, and Solutions 8.Space Complexity 8.1.Savitch's Theorem 8.2.The Class PSPACE 8.3.PSPACE-completeness The TQBF problem Winning strategies for games Generalized geography 8.4.The Classes L and NL 8.5.NL-completeness Searching in graphs 8.6.NL equals coNL 9.Intractability 9.1.Hierarchy Theorems Exponential space completeness 9.2.Relativization Limits of the diagonalization method 9.3.Circuit Complexity 10.Advanced Topics in Complexity Theory 10.1.Approximation Algorithms 10.2.Probabilistic Algorithms The class BPP Primality Read-once branching programs 10.3.Alternation Alternating time and space The Polynomial time hierarchy 10.4.Interactive Proof Systems Graph nonisomorphism Definition of the model IP =​ PSPACE 10.5.Parallel Computation Uniform Boolean circuits Contents note continued: The class NC P-completeness 10.6.Cryptography Secret keys Public-key cryptosystems One-way functions Trapdoor functions Exercises, Problems, and Solutions.
Item type:
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Shelving location Call number Status Date due Barcode Item holds
Books Books Gulbanoo Premji Library, Azim Premji University, Bengaluru 2nd Floor 511.35 SIP (Browse shelf(Opens below)) Available 34730
Books Books Gulbanoo Premji Library, Azim Premji University, Bengaluru 2nd Floor 511.35 SIP (Browse shelf(Opens below)) Available 34729
Total holds: 0

Includes bibliographical references (p. 415-419) and index.

Machine generated contents note: 0.Introduction
0.1.Automata, Computability, and Complexity
Complexity theory
Computability theory
Automata theory
0.2.Mathematical Notions and Terminology
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
0.3.Definitions, Theorems, and Proofs
Finding proofs
0.4.Types of Proof
Proof by construction
Proof by contradiction
Proof by induction
Exercises, Problems, and Solutions
pt. One Automata and Languages
1.Regular Languages
1.1.Finite Automata
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
1.2.Nondeterminism
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
1.3.Regular Expressions
Contents note continued: Formal definition of a regular expression
Equivalence with finite automata
1.4.Nonregular Languages
The pumping lemma for regular languages
2.Context-Free Languages
2.1.Context-Free Grammars
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
2.2.Pushdown Automata
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
2.3.Non-Context-Free Languages
The pumping lemma for context-free languages
2.4.Deterministic Context-Free Languages
Properties of DCFLs
Deterministic context-free grammars
Relationship of DPDAs and DCFGs
Parsing and LR(k) Grammars
pt. Two Computability Theory
3.The Church-Turing Thesis
3.1.Turing Machines
Formal definition of a Turing machine
Contents note continued: Examples of Turing machines
3.2.Variants of Turing Machines
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
3.3.The Definition of Algorithm
Hilbert's problems
Terminology for describing Turing machines
4.Decidability
4.1.Decidable Languages
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
4.2.Undecidability
The diagonalization method
An undecidable language
A Turing-unrecognizable language
5.Reducibility
5.1.Undecidable Problems from Language Theory
Reductions via computation histories
5.2.A Simple Undecidable Problem
5.3.Mapping Reducibility
Computable functions
Formal definition of mapping reducibility
6.Advanced Topics in Computability Theory
Contents note continued: 6.1.The Recursion Theorem
Self-reference
Terminology for the recursion theorem
Applications
6.2.Decidability of logical theories
A decidable theory
An undecidable theory
6.3.Turing Reducibility
6.4.A Definition of Information
Minimal length descriptions
Optimality of the definition
Incompressible strings and randomness
pt. Three Complexity Theory
7.Time Complexity
7.1.Measuring Complexity
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
7.2.The Class P
Polynomial time
Examples of problems in P
7.3.The Class NP
Examples of problems in NP
The P versus NP question
7.4.NP-completeness
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
7.5.Additional NP-complete Problems
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Contents note continued: Exercises, Problems, and Solutions
8.Space Complexity
8.1.Savitch's Theorem
8.2.The Class PSPACE
8.3.PSPACE-completeness
The TQBF problem
Winning strategies for games
Generalized geography
8.4.The Classes L and NL
8.5.NL-completeness
Searching in graphs
8.6.NL equals coNL
9.Intractability
9.1.Hierarchy Theorems
Exponential space completeness
9.2.Relativization
Limits of the diagonalization method
9.3.Circuit Complexity
10.Advanced Topics in Complexity Theory
10.1.Approximation Algorithms
10.2.Probabilistic Algorithms
The class BPP
Primality
Read-once branching programs
10.3.Alternation
Alternating time and space
The Polynomial time hierarchy
10.4.Interactive Proof Systems
Graph nonisomorphism
Definition of the model
IP =​ PSPACE
10.5.Parallel Computation
Uniform Boolean circuits
Contents note continued: The class NC
P-completeness
10.6.Cryptography
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Exercises, Problems, and Solutions.

There are no comments on this title.

to post a comment.

Maintained by Gulbanoo Premji Library, KRC

Azim Premji University

Total Visits to Site (September 2024 onwards):best free website hit counter