- ホーム
- > 洋書
- > 英文書
- > Computer / General
Full Description
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.
Contents
Preliminaries. Computability: Programs and Computable Functions. Primitive Recursive Functions. A Universal Program. Calculations on Strings. Turing Machines. Processes and Grammars. Classifying Unsolvable Problems. Grammars and Automata: Regular Languages. Context-Free Languages. Context-Sensitive Languages. Logic: Propositional Calculus. Quantification Theory. Complexity: Abstract Complexity. PolynomialTime Computability. Semantics: Approximation Orderings. Denotational Semantics of Recursion Equations. Operational Semantics of Recursion Equations. Suggestions for Further Reading. Subject Index.