Solving partial order constraints for LPO termination
Author
Codish, M; Lagoon, V; Stuckey, PJEditor
Pfenning, FDate
2006-01-01Source Title
TERM REWRITING AND APPLICATIONS, PROCEEDINGSPublisher
SPRINGER-VERLAG BERLINAffiliation
Computer Science and Software EngineeringMetadata
Show full item recordDocument Type
Conference PaperCitations
Codish, M., Lagoon, V. & Stuckey, P. J. (2006). Solving partial order constraints for LPO termination. Pfenning, F (Ed.) TERM REWRITING AND APPLICATIONS, PROCEEDINGS, 4098, pp.4-18. SPRINGER-VERLAG BERLIN. https://doi.org/10.1007/11805618_2.Access Status
This item is currently not available from this repositoryAbstract
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.
Keywords
Computer SoftwareExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References