DFKI Research Report-93-42
by Hubert Comon, Ralf Treinen
The First-Order Theory of Lexicographic Path Orderings is Undecidable
We show, under some assumption on the signature, that the fragment of the theory of any lexicographic path ordering is undecidable. This applies to partial and to total precedences. Our result implies in particular that the simplification rule of ordered completion is undecidable.
This document is available as PDF-File(15,1MB).
The next abstract is here, and the previous abstract is here.
Note: This page was written to look best with CSS stylesheet support Level 1 or higher. Since you can see this, your browser obviously doesn't support CSS, or you have turned it off. We highly recommend you use a browser that supports and uses CSS, and review this page once you do. However, don't fear, we've tried to write this page to still work and be readable without CSS.