A note on a canonical theory with undecidable unification and matching problem
type: Item
instance of: scholarly article
title: A note on a canonical theory with undecidable unification and matching problem
zbMATH Open document ID: 0637.68034
DOI: 10.1007/BF00247435
author: Alexander Bockmayr
published in: Journal of Automated Reasoning
publication date: 1987-01-01T00:00:00Z
review text: This research note gives a simple proof of the fact that the unification and matching problem is undecidable in the class of equational theories that can be embedded into a canonical term rewriting system. We present a canonical term rewriting system for integer arithmetic and show that the unification and matching problem in the corresponding equational theory is equivalent to Hilbert's tenth problem which is well known to be undecidable.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 4039277
zbMATH Keywords: undecidability
zbMATH Keywords: unification
zbMATH Keywords: matching
zbMATH Keywords: equational theories
zbMATH Keywords: canonical term rewriting system
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00247435
OpenAlex ID: W1993563396
Recommended article: The undecidability of the unification and matching problem for canonical theories
Recommended article: On equational theories, unification, and (un)decidability
Recommended article: The undecidability of the DA-unification problem
Recommended article: A remark on infinite matching vs infinite unification
Recommended article: Unification in permutative equational theories is undecidable
Recommended article: On unification: Equational theories are not bounded
Recommended article: Q3779785
Recommended article: The undecidability of the semi-unification problem
Recommended article: Unification problem in equational theories
Recommended article: On the undecidability of second-order unification
description: scientific article; zbMATH DE number 4039277