2006/08/06 by Harald Zankl, Zankl, Harald, Aart Middeldorp +1
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Symbolic Computation (cs.SC) #cs.LO #cs.SC
paper · pdf · doi:10.48550/arxiv.cs/0608032
15 pages
arxiv created 2007/04/03 · arxiv updated 2009/12/01
This paper presents two new approaches to prove termination of rewrite systems with the Knuth-Bendix order efficiently. The constraints for the weight function and for the precedence are encoded in (pseudo-)propositional logic and the resulting formula is tested for satisfiability. Any satisfying assignment represents a weight function and a precedence such that the induced Knuth-Bendix order orients the rules of the encoded rewrite system from left to right.