Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T23:51:20.140Z Has data issue: false hasContentIssue false

The undecidability of the DA-unification problem

Published online by Cambridge University Press:  12 March 2014

J. Siekmann
Affiliation:
Fachbereich Informatik, Universität Kaiserslautern, 6750 Kaiserslautern, West Germany
P. Szabó
Affiliation:
Standard Elektrik Lorenz Research Center, D-7530 Pforzheim, West Germany

Abstract

We show that the DA-uniflcation problem is undecidable. That is, given two binary function symbols ⊕ and ⊗, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following DA-axioms hold:

Two terms are DA-unifiable (i.e. an equation is solvable in DA) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory DA.

This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable