It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair

DOI10.1007/BFB0028998MaRDI QIDQ5096169zbMATH OpenFDO

Authors Paliath Narendran, Jonathan Stillman

Publication date 16 August 2022

Published in STACS 89 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028998

zbMATH Keywords

critical pairhalting problemTuring machine

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Recommendations

• The Knuth-Bendix Completion Procedure and Thue Systems
• scientific article; zbMATH DE number 3928345
• scientific article; zbMATH DE number 3850464
• scientific article; zbMATH DE number 3956435
• scientific article; zbMATH DE number 4016226

Cites work

• scientific article; zbMATH DE number 3860434 (Why is no real title available?)
• scientific article; zbMATH DE number 3930339 (Why is no real title available?)
• scientific article; zbMATH DE number 3956435 (Why is no real title available?)
• scientific article; zbMATH DE number 4047064 (Why is no real title available?)
• scientific article; zbMATH DE number 4074464 (Why is no real title available?)
• scientific article; zbMATH DE number 4092757 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• The undecidability of the unification and matching problem for canonical theories
• Unification in permutative equational theories is undecidable

Cited in

(2)

• Divergence phenomena during completion
• Chain properties of rule closures

This page was built for publication: It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair

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