Computability, Complexity, and Languages: Fundamentals of Theoretical Computer ScienceComputability, Complexity, and Languages is an introductory text that 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.
|
Contents
1 | |
15 | |
Grammars and Automata | 235 |
Logic | 345 |
Complexity | 417 |
Semantics | 465 |
Suggestions for Further Reading | 593 |
595 | |
599 | |
Other editions - View all
Common terms and phrases
accepts algorithm alphabet apply assignment assume automaton base begin belongs bound called Chapter clauses clearly complete configuration consider consists constant construct contains context-free grammar continuous corresponding course data structure defined definition derivation determine element equation example Exercise exists fact Finally finite formula Give given GOTO halts Hence implies induction infinite initial input instruction labeled language least Lemma length literal macro mean Note obtained occur operations otherwise pair partial order particular predicate problem productions Proof proof of Theorem Prove quadruples replace represents respectively result satisfiable sentence sequence Show statement steps string structure subset Suppose symbol tape term terminals Theorem Theorem 2.1 theory tion transition true Turing machine universal unsatisfiable variables W-structure write