Proving termination using recursive path orders and SAT solving

Peter Schneider-Kamp*, René Thiemann, Elena Annov, Michael Codish, Jürgen Giesl

*Kontaktforfatter for dette arbejde

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

We introduce a propositional encoding of the recursive path order with status (RPO). RPO is a combination of a multiset path order and a lexicographic path order which considers permutations of the arguments in the lexicographic comparison. Our encoding allows us to apply SAT solvers in order to determine whether a given term rewrite system is RPO-terminating. Furthermore, to apply RPO within the dependency pair framework, we combined our novel encoding for RPO with an existing encoding for argument filters. We implemented our contributions in the termination prover AProVE. Our experiments show that due to our encoding, combining termination provers with SAT solvers improves the performance of RPO-implementations by orders of magnitude.

OriginalsprogEngelsk
TitelFrontiers of Combining Systems - 6th International Symposium, FroCoS 2007, Proceedings
Antal sider16
Publikationsdato1. dec. 2007
Sider267-282
ISBN (Trykt)9783540746201
StatusUdgivet - 1. dec. 2007
Begivenhed6th International Symposium on Frontiers of Combining Systems, FroCoS 2007 - Liverpool, Storbritannien
Varighed: 10. sep. 200712. sep. 2007

Konference

Konference6th International Symposium on Frontiers of Combining Systems, FroCoS 2007
LandStorbritannien
ByLiverpool
Periode10/09/200712/09/2007
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind4720 LNAI
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Proving termination using recursive path orders and SAT solving'. Sammen danner de et unikt fingeraftryk.

Citationsformater