Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Matrix Interpretations for Proving Termination of Term Rewriting

Matrix Interpretations for Proving Termination of Term Rewriting We present a new method for automatically proving termination of term rewriting. It is based on the well-known idea of interpretation of terms where every rewrite step causes a decrease, but instead of the usual natural numbers we use vectors of natural numbers, ordered by a particular nontotal well-founded ordering. Function symbols are interpreted by linear mappings represented by matrices. This method allows us to prove termination and relative termination. A modification of the latter, in which strict steps are only allowed at the top, turns out to be helpful in combination with the dependency pair transformation. By bounding the dimension and the matrix coefficients, the search problem becomes finite. Our implementation transforms it to a Boolean satisfiability problem (SAT), to be solved by a state-of-the-art SAT solver. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Automated Reasoning Springer Journals

Matrix Interpretations for Proving Termination of Term Rewriting

Loading next page...
 
/lp/springer-journals/matrix-interpretations-for-proving-termination-of-term-rewriting-00nx2EmMDK

References (27)

Publisher
Springer Journals
Copyright
Copyright © 2007 by Springer Science+Business Media B.V.
Subject
Computer Science; Symbolic and Algebraic Manipulation ; Mathematical Logic and Foundations; Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages
ISSN
0168-7433
eISSN
1573-0670
DOI
10.1007/s10817-007-9087-9
Publisher site
See Article on Publisher Site

Abstract

We present a new method for automatically proving termination of term rewriting. It is based on the well-known idea of interpretation of terms where every rewrite step causes a decrease, but instead of the usual natural numbers we use vectors of natural numbers, ordered by a particular nontotal well-founded ordering. Function symbols are interpreted by linear mappings represented by matrices. This method allows us to prove termination and relative termination. A modification of the latter, in which strict steps are only allowed at the top, turns out to be helpful in combination with the dependency pair transformation. By bounding the dimension and the matrix coefficients, the search problem becomes finite. Our implementation transforms it to a Boolean satisfiability problem (SAT), to be solved by a state-of-the-art SAT solver.

Journal

Journal of Automated ReasoningSpringer Journals

Published: Dec 11, 2007

There are no references for this article.