Computability, complexity, and languages : fundamentals of theoretical computer science

Martin D. Davis, Ron Sigal, Elaine J. Weyuker

This introductory text 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. Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page. The number of exercises included has more than tripled. Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.

「Nielsen BookData」より


  • 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. Polynomial Time Computability. Semantics: Approximation Orderings. Denotational Semantics of Recursion Equations. Operational Semantics of Recursion Equations. Suggestions for Further Reading. Subject Index.

「Nielsen BookData」より


書名 Computability, complexity, and languages : fundamentals of theoretical computer science
著作者等 Davis, Martin
Sigal, Ron
Weyuker, Elaine J
Weyuker Elaine J.
シリーズ名 Computer science and scientific computing
出版元 Academic Press
刊行年月 c1994
版表示 2nd. ed
ページ数 xix, 609 p.
大きさ 24 cm
ISBN 0122063821
NCID BA22456871
※クリックでCiNii Booksを表示
言語 英語
出版国 アメリカ合衆国