Solving Partial Order Constraints for LPO Termination

Details Solving Partial Order Constraints for LPO Termination Solving Partial Order Constraints for LPO Termination

2005-12-16

arxiv.org/abs/cs/0512067v1

Journal of Satisfiability, Boolean Modeling and Computation, 5:193-215: 2008

Computer Science

Programming Languages

15 pages, 2 figures, 2 tables

Scientific paper

This paper introduces a new kind of propositional encoding for reasoning about partial orders. The symbols in an unspecified partial order are viewed as variables which take integer values and are interpreted as indices in the order. For a partial order statement on n symbols each index is represented in log2 n propositional variables and partial order constraints between symbols are modeled on the bit representations. We illustrate the application of our approach to determine LPO termination for term rewrite systems. Experimental results are unequivocal, indicating orders of magnitude speedups in comparison with current implementations for LPO termination. The proposed encoding is general and relevant to other applications which involve propositional reasoning about partial orders.

Affiliated with

Also associated with

No associations

Rating

Solving Partial Order Constraints for LPO Termination 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 Solving Partial Order Constraints for LPO Termination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Partial Order Constraints for LPO Termination will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-112136