Advanced Topics in Term Rewriting

Enno Ohlebusch (Autor)

Buch | Softcover

414 Seiten

2010 | Softcover reprint of hardcover 1st ed. 2002
Springer-Verlag New York Inc.
978-1-4419-2921-1 (ISBN)

Artikel merken

Term rewriting techniques are applicable in various fields of computer sci ence: in software engineering (e.g., equationally specified abstract data types), in programming languages (e.g., functional-logic programming), in computer algebra (e.g., symbolic computations, Grabner bases), in pro gram verification (e.g., automatically proving termination of programs), in automated theorem proving (e.g., equational unification), and in algebra (e.g., Boolean algebra, group theory). In other words, term rewriting has applications in practical computer science, theoretical computer science, and mathematics. Roughly speaking, term rewriting techniques can suc cessfully be applied in areas that demand efficient methods for reasoning with equations. One of the major problems one encounters in the theory of term rewriting is the characterization of classes of rewrite systems that have a desirable property like confluence or termination. If a term rewriting system is conflu ent, then the normal form of a given term is unique. A terminating rewrite system does not permit infinite computations, that is, every computation starting from a term must end in a normal form. Therefore, in a system that is both terminating and confluent every computation leads to a result that is unique, regardless of the order in which the rewrite rules are applied. This book provides a comprehensive study of termination and confluence as well as related properties.

1 Motivation.- 2 Abstract Reduction Systems.- 3 Term Rewriting Systems.- 4 Confluence.- 5 Termination.- 6 Relative Undecidability.- 7 Conditional Rewrite Systems.- 8 Modularity.- 9 Graph Rewriting.- 10 Proving Termination of Logic Programs.- A Kruskal’s Theorem.- A.l Partial Well-Orderings.- A.2 A Proof of Kruskal’s Theorem.- References.

Erscheint lt. Verlag	3.12.2010
Zusatzinfo	XVI, 414 p.
Verlagsort	New York, NY
Sprache	englisch
Maße	155 x 235 mm
Themenwelt	Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
	Informatik ► Theorie / Studium ► Algorithmen
	Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
ISBN-10	1-4419-2921-5 / 1441929215
ISBN-13	978-1-4419-2921-1 / 9781441929211
Zustand	Neuware