Path of subterms ordering and recursive decomposition ordering revisited

DOI10.1016/S0747-7171(87)80023-8MaRDI QIDQ1099655zbMATH OpenOpenAlexFDO

Authors Michaël Rusinowitch

Publication date 1987

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0747-7171(87)80023-8

zbMATH Keywords

computing of normal formsrecursive decomposition orderingrecursive path orderingrewriting systemssubterms ordering

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Review text

The relationship between several simplification orderings is investigated: the path of subterms ordering, the recursive path ordering and the recursive decomposition ordering. The recursive decomposition ordering is improved in order to deal with more pairs of terms, and is made more efficient and easier to handle, by removing useless computations.

Recommendations

• scientific article; zbMATH DE number 3921961
• On the recursive decomposition ordering with lexicographical status and other related orderings
• Extensions and comparison of simplification orderings
• Simplification orderings: Putting them to the test
• Solving simplification ordering constraints

Cites work

• scientific article; zbMATH DE number 3870584 (Why is no real title available?)
• scientific article; zbMATH DE number 3810909 (Why is no real title available?)
• scientific article; zbMATH DE number 3821100 (Why is no real title available?)
• scientific article; zbMATH DE number 3905845 (Why is no real title available?)
• On multiset orderings
• Orderings for term-rewriting systems
• Proving termination with multiset orderings

Cited in

(16)

• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Rewrite orderings for higher-order terms in \(\eta\)-long \(\beta\)-normal form and the recursive path ordering
• Simplification orderings: Putting them to the test
• An improved general path order
• A Lambda-Free Higher-Order Recursive Path Order
• Polymorphic higher-order recursive path orderings
• scientific article; zbMATH DE number 3921961 (Why is no real title available?)
• scientific article; zbMATH DE number 604876 (Why is no real title available?)
• scientific article; zbMATH DE number 1104447 (Why is no real title available?)
• Extensions and comparison of simplification orderings
• Time bounded rewrite systems and termination proofs by generalized embedding
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Improving associative path orderings
• On the complexity of recursive path orderings
• Termination by completion
• On the recursive decomposition ordering with lexicographical status and other related orderings

This page was built for publication: Path of subterms ordering and recursive decomposition ordering revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099655)