Canonical Equational Proofs Softcover Repri Edition Contributor(s): Bachmair (Author) |
|
ISBN: 0817635556 ISBN-13: 9780817635558 Publisher: Birkhauser OUR PRICE: $52.24 Product Type: Paperback Published: June 1991 |
Additional Information |
BISAC Categories: - Mathematics | Logic |
Dewey: 511.3 |
LCCN: 91-11461 |
Series: Progress in Theoretical Computer Science |
Physical Information: 0.33" H x 6.14" W x 9.21" (0.49 lbs) 138 pages |
Descriptions, Reviews, Etc. |
Publisher Description: Equations occur in many computer applications, such as symbolic compu- tation, functional programming, abstract data type specifications, program verification, program synthesis, and automated theorem proving. Rewrite systems are directed equations used to compute by replacing subterms in a given formula by equal terms until a simplest form possible, called a normal form, is obtained. The theory of rewriting is concerned with the compu- tation of normal forms. We shall study the use of rewrite techniques for reasoning about equations. Reasoning about equations may, for instance, involve deciding whether an equation is a logical consequence of a given set of equational axioms. Convergent rewrite systems are those for which the rewriting process de- fines unique normal forms. They can be thought of as non-deterministic functional programs and provide reasonably efficient decision procedures for the underlying equational theories. The Knuth-Bendix completion method provides a means of testing for convergence and can often be used to con- struct convergent rewrite systems from non-convergent ones. We develop a proof-theoretic framework for studying completion and related rewrite- based proof procedures. We shall view theorem provers as proof transformation procedures, so as to express their essential properties as proof normalization theorems. |