scientific article; zbMATH DE number 4210102

MaRDI QIDQ3358706zbMATH OpenFDO

Authors Ralf Treinen

Publication date 1990

zbMATH Keywords

first-order theoriespartial lexicographic path orderingreduction of Post's Correspondence Problem to the decision problem of a theoryterm algebraundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) Artificial intelligence (68T99)

Recommendations

• A new method for undecidability proofs of first order theories
• The first-order theory of one-step rewriting is undecidable
• The first-order theory of lexicographic path orderings is undecidable
• Undecidability of the first order theory of one-step right ground rewriting
• The first-order theory of linear one-step rewriting is undecidable

Cited in

(14)

• A new method for undecidability proofs of first order theories
• The \(\exists^*\forall^*\) part of the theory of ground term algebra modulo an AC symbol is undecidable.
• Undecidability without arithmetization
• On the logic of reducibility: Axioms and examples
• Thue trees
• scientific article; zbMATH DE number 1400048 (Why is no real title available?)
• Open problems in rewriting
• Encompassment properties and automata with constraints
• More problems in rewriting
• Problems in rewriting III
• The first-order theory of one-step rewriting is undecidable
• Synthetic Undecidability and Incompleteness of First-Order Axiom Systems in Coq
• On first-order theorem proving using generalized odd-superpositions II
• Complete axiomatizations of some quotient term algebras

This page was built for publication:

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