Vi visar, under något antagande på signaturen, att det 9 8 fragmentet av teorin om en lexikografisk vägordning är obeslutbart, både i de partiella och i de totala prioritetsfallen. Vårt resultat innebär i synnerhet att det är obeslutsamt att förenkla regeln om beordrat slutförande.
Comon och Treinen visar första ordningens teori om lexikografisk vägbeställning är obeslutsam REF.
The First-Order Theory of Lexicographic Path Orderings is Undecidable
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}