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.

What people are saying  Write a review
We haven't found any reviews in the usual places.
Contents
1  
15  
Grammars and Automata  235 
Logic  345 
Complexity  417 
Semantics  465 
Suggestions for Further Reading  593 
595  
599  
Other editions  View all
Computability, Complexity, and Languages: Fundamentals of Theoretical ... Martin Davis,Ron Sigal,Elaine J. Weyuker No preview available  1994 
Common terms and phrases
accepts algorithm alphabet assignment belongs Bool called Chapter Chomsky normal form CNF formula constant symbol contains contextfree grammar contextfree language contextsensitive Corollary data structure system defined definition denoted derivation tree element equation example Exercise fixed point function f function symbol FV(P Gcomputable Give given GOTO halts Hence implies induction hypothesis infinite initial input instruction integer labeled Lemma let f linear bounded automaton ndfa nondeterministic Turing machine NPcomplete obtained operational semantics otherwise pair parameter theorem partial function partial order partially computable function PostTuring 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 semiThue process sequence Show string subset terminals Theorem 2.1 total function unary unsatisfiable upper bound Wprogram Wterm word write