Warehouse Stock Clearance Sale

Grab a bargain today!


Models of Computation and Formal Languages
By

Rating

Product Description
Product Details

Table of Contents

Preface
0.: Mathematical Preliminaries
.1: Sets and Set-Forming Operations
.2: Introduction to Formal Language Theory
.3: Mappings and Functions
.4: Defining Functions Recursively
.5: The Mathematics of Big-O Notation
.6: Mathematical Induction
.7: Graphs
.8: Introduction to Propositional Logic
.9: Two Important Proof Techniques
.10: Defining Sets Recursively
.11: Infinite Sets
.12: Conjunctive Normal Form
.13: Number-Theoretic Predicates
.14: Further Reading
Part I MODELS OF COMPUTATION
1 .: Turing Machines
1.1: What Is Computation?
1.2: An Informal Description of Turing Machines
1.3: The Formal Definition of Turing Machines
1.4: Turing Machines as Language Acceptors and as Language Recognizers
1.5: Turing Machines as Computers of Number-Theoretic Functions
1.6: Modular Construction of Turing Machines
1.7: Introduction to Complexity Theory
1.8: Suggestions for Further Reading
2: Additional Varieties of Turing Machines
2.1: Turing Machines with One-Way-Infinite Tape
2.2: Turing Machines that Accept by Terminal Stare
2.3: Multitape Turing Machines
2.4: Encoding of Turing Machines
2.5: Universal Turing Machines
2.6: Nondeterministic Turing Machines
2.7: A Number-Theoretic FUnction That Is Not Turing-Computable
2.8: Turing Machines and Artificial Intelligence
2.9: Turing Machines and Cognitive Science
2.10: Regarding Theoretical Computer Science and Number-Theoretic Functions
2.11: Further Reading
3: An Introduction to Recursion Theory
3.1: The Primitive Recursive Functions
3.2: Primitive Recursive Predicates
3.3: The Partial Recursive Functions
3.4: The Class of Partial Recursive Functions Is Identical to the Class of Turing-Computable Functions
3.5: Recursive Sets
3.6: Recursively Enumerable Sets
3.7: Historical Remarks and Suggestions for Further Reading
4: Markov Algorithms
4.1: An Alternative Model of Sequential Computation
4.2: Markov Algorithms as Language Acceptors and as Language Recognizers
4.3: Markov Algorithms as Computers of Number-Theoretic Functions
4.4: Labeled Markov Algorithms
4.5: The Class of Markov-Computable Functions Is Identical to the Class of Partial Recursive Functions
4.6: Considerations of Efficiency
4.7: Computation Theory and the Foundations of Mathematics
4.8: Bibliography
5: Register Machines
5.1: Register Machines
5.2: The Class of Register-Machine-Computable Functions Is Identical to the Class of Partial Recursive Functions
5.3: Register Machines and Formal Languages
5.4: A Model-Independent Characterization of Computational Feasibility
5.5: Final Remarks and Suggestions for Further Reading
6: Post Systems (Optional)
6.1: Post Systems and Formal Languages
6.2: The Class of Post-Computable Functions Is Identical to the Class of Partial Recursive Functions
6.3: Closure Properties of the Class of Languages Generated by Post Systems
6.4: The Class of Languages Generated by Post Systems Is Identical to the Class of Turing-Acceptable Languages
6.5: Language Recognition and Post Systems
6.6: What Is a Model of Computation?
7.: The Vector Machine Model of Parallel Computation (Optional)
7.1: What Is Parallel Computation?
7.2: Vectors and Vector Operations
7.3: Vector Machines
7.4: Vector Machines and Function Computation
7.5: Vector Machines and Formal Languages
7.6: Parallel Computation and Cognitive Science
7.7: Further Remarks
8.: The Bounds of Computability
8.1: The Church-Turing Thesis
8.2: The Bounds of Computability-in-Principle: The Self-Halting Problem for Turing Machines
8.3: The Bounds of Computability-in-Principle: The Halting Problem for Turing Machines
8.4: The Bounds of Computability-in-Principle: Rice's Theorem
8.5: The Bounds of Feasible Computation: The Concept of NP-Completeness
8.6: An NP-Complete Problem (Cook-Levin Theorem)
8.7: Other NP-Complete Problems
8.8: The Bounds of Parallel Computation: The Concept of P-Completeness (Advanced)
8.9: A P-Complete Problem (Ladner's Theorem) (Advanced)
8.10: The Nearest-Neighbor Traveling Salesman Problem is P-Complete (Advanced)
8.11: Beyond Symbol Processing: The Connectionist Model of Cognition
8.12: Summary, Historical Remarks, and Suggestions for Further Reading
Part II FORMAL LANGUAGES AND AUTOMATA9.: Regular Languages and Finite-State Automata
9.1: Regular Expressions and Regular Languages
9.2: Deterministic Finite-State Automata
9.3: Nondeterministic Finite-State Automata
9.4: A Pumping Lemma for FSA-Acceptable Languages
9.5: Closure Properties of the Family of FSA-Acceptable Languages
9.6: The Family of Regular Languages Is Identical to the Family of FSA-Acceptable Languages
9.7: Finite-State Automata with Epsilon-Moves
9.8: Generative Grammars
9.9: Right-Linear Grammars and Regular Languages
9.10: Summary, Historical Remarks and Suggestions for Further Reading
10.: Context-Free Languages and Pushdown-Stack Automata
10.1: Context-Free Grammars and Natural Languages
10.2: Normal Forms for Context-Free Grammars
10.3: Pushdown-Stack Automata
10.4: An Equivalent Notion of Word Acceptance for Pushdown-Stack Automata
10.5: The Class of Context-Free Languages Is Identical to the Class of PSA-Acceptable Languages
10.6: Closure Properties of the Family of Context-Free Languages
10.7: A Pumping Lemma for Context-Free Languages
10.8: Deterministic Context-Free Languages
10.9: Decidability Results for Context-Free Languages
10.10: Bibliography and Suggestions for Further Reading
11.: Context-Sensitive Languages and Linear-Bounded Automata
11.1: Context-Sensitive Grammars
11.2: A Normal Form for Context-Sensitive Grammars
11.3: Linear-Bounded Automata
11.4: Context-Sensitive Languages and Linear-Bounded Automata
11.5: Closure Properties of the Family of Context-Sensitive Languages
11.6: The General Word Problem for Context-Sensitive Languages Is Solvable
11.7: There Exist Turing-Recognizable Languages That Are Not Context-Sensitive
11.8: Final Remarks
12.: Generative Grammars and the Chomsky Hierarchy
12.1: Turing Machines and Phrase-Structure Languages
12.2: Closure Properties of the Family of Phrase-Structure Languages
12.3: Turing Machiens as Language Enumerators
12.4: A Recursion-Theoretic Characterization of the Family of Phrase-Structure Languages
12.5: The General Word Problem for Phrase-Structure Languages Is Unsolvable
12.6: The Post Correspondence Problem
12.7: The Chomsky Hierachy
Epilogue
Bibliography
Index

About the Author

R. Gregory Taylor holds degrees from the University of Michigan, New York University, and Columbia University. He is currently chair of the Department of Computer Science at Jersey City State College.

Ask a Question About this Product More...
 
Look for similar items by category
People also searched for
This title is unavailable for purchase as none of our regular suppliers have stock available. If you are the publisher, author or distributor for this item, please visit this link.

Back to top