04265nam 2200625 450 991082823510332120230214003117.01-4832-6458-0(CKB)3710000000200571(EBL)1901552(SSID)ssj0001266601(PQKBManifestationID)12541682(PQKBTitleCode)TC0001266601(PQKBWorkID)11267926(PQKB)11548653(MiAaPQ)EBC1901552(EXLCZ)99371000000020057120150202h19831983 uy 0engur|n|---|||||txtccrComputability, complexity, and languages fundamentals of theoretical computer science /Martin D. Davis, Elaine J. WeyukerNew York, New York ;London, [England] :Academic Press,1983.©19831 online resource (448 p.)Computer Science and Applied MathematicsDescription based upon print version of record.1-322-55867-1 0-12-206380-5 Includes bibliographical references and index.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 Functions4. Post-Turing ProgramsCHAPTER 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 Problems; 4. Post's Correspondence Problem; 5. Grammars; 6. Some Unsolvable Problems Concerning Grammars; 7. Recursion and Minimalization; 8. Normal Processes9. A Non-R.E. SetPART 2: GRAMMARS AND AUTOMATA; CHAPTER 8. Regular Languages; 1. Finite Automata; 2. Nondeterministic Finite Automata; 3. Additional Examples; 4. Closure Properties; 5. Kleene's Theorem; 6. The Pumping Lemma and Its Applications; 7. The Myhill-Nerode Theorem; CHAPTER 9. 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 LanguagesCHAPTER 10. Context-Sensitive Languages1. The Chomsky Hierarchy; 2. Linear Bounded Automata; 3. Closure Properties; PART 3: LOGIC; CHAPTER 11. Propositional Calculus; 1. Formulas and Assignments; 2. Tautological Inference; 3. Normal Forms; 4. The Davis-Putnam Rules; 5. Minimal Unsatisfiability and Subsumption; 6. Resolution; 7. The Compactness Theorem; CHAPTER 12. Quantification Theory; 1. The Language of Predicate Logic; 2. Semantics; 3. Logical Consequence; 4. Herbrand's Theorem; 5. Unification; 6. Compactness and Countability; 7. Gödel's Incompleteness Theorem8. Unsolvability of the Satisfiability Problem in Predicate LogicComputability, Complexity, and LanguagesComputer science and applied mathematics.Machine theoryComputational complexityFormal languagesMachine theory.Computational complexity.Formal languages.511.3Davis Martin1928-2023,1276157Weyuker Elaine J.MiAaPQMiAaPQMiAaPQBOOK9910828235103321Computability, complexity, and languages4115380UNINA