UID:
edoccha_9960072759402883
Format:
1 online resource (xix, 609 pages)
Edition:
2nd ed.
ISBN:
1-283-61890-7
,
0-08-050246-6
,
9786613931351
Series Statement:
Computer Science and Scientific Computing
Content:
This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.* Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a ""universal"" program that takes up less than a page.* The number of exercises included has more than tripled.* Automata theory, computational logic, and complexit
Note:
Description based upon print version of record.
,
Front Cover; Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science; Copyright Page; Dedication; Table of Contents; Preface; Acknowledgments; Dependency Graph; Chapter 1. Preliminaries; 1. Sets and n-tuples; 2. Functions; 3. Alphabets and Strings; 4. Predicates; 5. Quantifiers; 6. Proof by Contradiction; 7. Mathematical Induction; Part 1: Computability; Chapter 2. Programs and Computable Functions; 1. A Programming Language; 2. Some Examples of Programs; 3. Syntax; 4. Computable Functions; 5. More about Macros; Chapter 3. Primitive Recursive Functions
,
1. Composition2. Recursion; 3. PRC Classes; 4. Some Primitive Recursive Functions; 5. Primitive Recursive Predicates; 6. Iterated Operations and Bounded Quantifiers; 7. Minimalization; 8. Pairing Functions and Gödel Numbers; Chapter 4. A Universal Program; 1. Coding Programs by Numbers; 2. The Halting Problem; 3. Universality; 4. Recursively Enumerable Sets; 5. The Parameter Theorem; 6. Diagonalization and Reducibility; 7. Rice's Theorem; *8. The Recursion Theorem; *9. A Computable Function That Is Not Primitive Recursive; Chapter 5. Calculations on Strings
,
1. Numerical Representation of Strings2. A Programming Language for String Computations; 3. The Languages L and Ln; 4. Post-Turing Programs; 5. Simulation of Ln in F; 6. Simulation of F in L; Chapter 6. Turing Machines; 1. Internal States; 2. A Universal Turing Machine; 3. The Languages Accepted by Turing Machines; 4. The Halting Problem for Turing Machines; 5. Nondeterministic Turing Machines; 6. Variations on the Turing Machine Theme; Chapter 7. Processes and Grammars; 1. Semi-Thue Processes; 2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes
,
3. Unsolvable Word Problems4. Post's Correspondence Problem; 5. Grammars; 6. Some Unsolvable Problems Concerning Grammars; *7. Normal Processes; Chapter 8. Classifying Unsolvable Problems; 1. Using Oracles; 2. Relativization of Universality; 3. Reducibility; 4. Sets r.e. Relative to an Oracle; 5. The Arithmetic Hierarchy; 6. Post's Theorem; 7. Classifying Some Unsolvable Problems; 8. Rice's Theorem Revisited; 9. Recursive Permutations; Part 2: Grammars and Automata; Chapter 9. Regular Languages; 1. Finite Automata; 2. Nondeterministic Finite Automata; 3. Additional Examples
,
4. Closure Properties5. Kleene's Theorem; 6. The Pumping Lemma and Its Applications; 7. The Myhill-Nerode Theorem; Chapter 10. Context-Free Languages; 1. Context-Free Grammars and Their Derivation Trees; 2. Regular Grammars; 3. Chomsky Normal Form; 4. Bar-Hillel's Pumping Lemma; 5. Closure Properties; *6. Solvable and Unsolvable Problems; 7. Bracket Languages; 8. Pushdown Automata; 9. Compilers and Formal Languages; Chapter 11. Context-Sensitive Languages; 1. The Chomsky Hierarchy; 2. Linear Bounded Automata; 3. Closure Properties; Part 3: Logic; Chapter 12. Propositional Calculus
,
1. Formulas and Assignments
,
English
Additional Edition:
ISBN 1-4933-0034-2
Additional Edition:
ISBN 0-12-206382-1
Language:
English
Bookmarklink
