Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science
Computability, 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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
accepts algorithm alphabet assignment belongs Bool called Chapter Chomsky normal form CNF formula constant symbol contains context-free grammar context-free language context-sensitive Corollary data structure system defined definition denoted derivation tree element equation example Exercise fixed point function f function symbol FV(P G-computable Give given GOTO halts Hence implies induction hypothesis infinite initial input instruction integer labeled Lemma let f linear bounded automaton ndfa nondeterministic Turing machine NP-complete obtained operational semantics otherwise pair parameter theorem partial function partial order partially computable function Post-Turing program PRC class predicate primitive recursive functions problem productions proof of Theorem prove Theorem pushdown automaton quadruples r.e. set regular language result satisfiable Section semantics semi-Thue process sequence Show string subset terminals Theorem 2.1 total function unary unsatisfiable upper bound W-program W-term word write