The first-order theory of lexicographic path orderings is undecidable

DOI10.1016/S0304-3975(96)00049-7zbMath0903.68107OpenAlexW1963801750MaRDI QIDQ1392274

Ralf Treinen, Hubert Comon

Publication date: 23 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00049-7

zbMATH Keywords

lexicographic path ordering

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Problems in rewriting III, Unnamed Item, Theories of orders on the set of words, How to win a game with features

Cites Work

• Simple LPO constraint solving methods
• Termination of rewriting
• Equational problems and disunification
• A new method for undecidability proofs of first order theories
• About the theory of tree embedding
• Open problems in rewriting
• More problems in rewriting
• SOLVING SYMBOLIC ORDERING CONSTRAINTS
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item