文档介绍：theory-
An Introduction to the Theory of
Computation
Eitan Gurari, Ohio State University
Computer Science Press, 1989, ISBN 0-7167-8182-4
Copyright © Eitan M. Gurari
To Shaula, Inbal, Itai, Erez, Netta, and Danna
Preface
1 GENERAL CONCEPTS
Alphabets, Strings, and Representations
Formal Languages and Grammars
Programs
Problems
Reducibility among Problems
Exercises
Bibliographic Notes
2 FINITE-MEMORY PROGRAMS
Motivation
Finite-State Transducers
Finite-State Automata and Regular Languages
Limitations of Finite-Memory Programs
Closure Properties for Finite-Memory Programs
Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
3 RECURSIVE FINITE-DOMAIN PROGRAMS
Recursion
Pushdown Transducers
Context-Free Languages
Limitations of Recursive Finite-Domain Programs
Closure Properties for Recursive Finite-Domain Programs
Decidable Properties for Recursive Finite-Domain Programs
Exercises
o-/~gurari/theory-bk/theory- (1 of 3) [2/24/2003 1:46:54 PM]
theory-
Bibliographic Notes
4 GENERAL PROGRAMS
Turing Transducers
Programs and Turing Transducers
Nondeterminism versus Determinism
Universal Turing Transducers
Undecidability
Turing Machines and Type 0 Languages
Post's Correspondence Problem
Exercises
Bibliographic Notes
5 RESOURCE-PUTATION
Time and Space
A Time Hierarchy
Nondeterministic Polynomial Time
More plete Problems
Polynomial Space
plete Problems
Exercises
Bibliographic Notes
6 PUTATION
Error-Free Probabilistic Programs
Probabilistic Programs That Might Err
Probabilistic Turing Transducers
Probabilistic Polynomial Time
Exercises
Bibliographic Notes
7 PUTATION
Parallel Programs
Parallel Random Access Machines