Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

The First-Order Theory of Lexicographic Path Orderings is Undecidable

Hubert Comon, Ralf Treinen

Theoretical Computer Science, April 1997

fragment of the theory of a lexicographic path ordering is undecidable, both in the partial and in the total precedence cases. Our result implies in particular that the simplification rule of ordered completion is undecidable.

Download PDF        Show BibTeX               

@ARTICLE{comon95tcs,
  title = {The First-Order Theory of Lexicographic Path                         Orderings is Undecidable},
  author = {Hubert Comon and Ralf Treinen},
  year = {1997},
  month = {apr},
  journal = {{Theoretical Computer Science}},
  note = {{To Appear}},
}

Login to edit