SAT Solving for Argument Filterings

Details SAT Solving for Argument Filterings SAT Solving for Argument Filterings

2006-05-17

arxiv.org/abs/cs/0605074v1

Computer Science

Logic in Computer Science

Scientific paper

This paper introduces a propositional encoding for lexicographic path orders in connection with dependency pairs. This facilitates the application of SAT solvers for termination analysis of term rewrite systems based on the dependency pair method. We address two main inter-related issues and encode them as satisfiability problems of propositional formulas that can be efficiently handled by SAT solving: (1) the combined search for a lexicographic path order together with an \emph{argument filtering} to orient a set of inequalities; and (2) how the choice of the argument filtering influences the set of inequalities that have to be oriented. We have implemented our contributions in the termination prover AProVE. Extensive experiments show that by our encoding and the application of SAT solvers one obtains speedups in orders of magnitude as well as increased termination proving power.

Affiliated with

Also associated with

No associations

Rating

SAT Solving for Argument Filterings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with SAT Solving for Argument Filterings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and SAT Solving for Argument Filterings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-489524