Skip to content

Mathematical Theory of Computation

Spend $50 to get a free DVD!

ISBN-10: 0486432386

ISBN-13: 9780486432380

Edition: 2003

Authors: Zohar Manna

List price: $24.95
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

With the objective of making into a science the art of verifying computer programs (debugging), the author addresses both practical and theoretical aspects. Subjects include computability (with discussions of finite automata and Turing machines); predicate calculus; verification of programs (bloth flowchart and algol-like programs); flowchart schemas; and the fixpoint theory of programs. 1974 edition. 77 figures.
Customers also bought

Book details

List price: $24.95
Copyright year: 2003
Publisher: Dover Publications, Incorporated
Publication date: 12/24/2003
Binding: Paperback
Pages: 480
Size: 5.25" wide x 8.25" long x 0.80" tall
Weight: 1.276
Language: English

Preface
Computability
Introduction
Finite Automata
Regular Expressions
Finite Automata
Transition Graphs
Kleene's Theorem
The Equivalence Theorem
Turing Machines
Turing Machines
Post Machines
Finite Machines with Pushdown Stores
Nondeterminism
Turing Machines as Acceptors
Recursively Enumerable Sets
Recursive Sets
Formal Languages
Turing Machines as Generators
Primitive Recursive Functions
Partial Recursive Functions
Turing Machines as Algorithms
Solvability of Classes of Yes/No Problems
The Halting Problem of Turing Machines
The Word Problem of Semi-Thue Systems
Post Correspondence Problem
Partial Solvability of Classes of Yes/No Problems
Bibliographic Remarks
References
Problems
Predicate Calculus
Introduction
Basic Notions
Syntax
Semantics (Interpretations)
Valid Wffs
Equivalence of Wffs
Normal Forms of Wffs
The Validity Problem
Natural Deduction
Rules for the Connectives
Rules for the Quantifiers
Rules for the Operators
The Resolution Method
Clause Form
Herbrand's Procedures
The Unification Algorithm
The Resolution Rule
Bibliographic Remarks
References
Problems
Verification of Programs
Introduction
Flowchart Programs
Partial Correctness
Termination
Flowchart Programs with Arrays
Partial Correctness
Termination
Algol-Like Programs
While Programs
Partial Correctness
Total Correctness
Bibliographic Remarks
References
Problems
Flowchart Schemas
Introduction
Basic Notions
Syntax
Semantics (Interpretations)
Basic Properties
Herbrand Interpretations
Decision Problems
Unsolvability of the Basic Properties
Free Schemas
Tree Schemas
Ianov Schemas
Formalization in Predicate Calculus
The Algorithm
Formalization of Properties of Flowchart Programs
Formalization of Properties of Flowchart Schemas
Translation Problems
Recursive Schemas
Flowchart Schemas versus Recursive Schemas
Bibliographic Remarks
References
Problems
The Fixpoint Theory of Programs
Introduction
Functions and Functionals
Monotonic Functions
Continuous Functionals
Fixpoints of Functionals
Recursive Programs
Computation Rules
Fixpoint Computation Rules
Systems of Recursive Defintions
Verification Methods
Stepwise Computational Induction
Complete Computational Induction
Fixpoint Induction
Structural Induction
Bibliographic Remarks
References
Problems
Indexes
Name Index
Subject Index