Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T11:43:07.075Z Has data issue: false hasContentIssue false
  • English
  • Français

The undecidability of the DA-unification problem

Published online by Cambridge University Press:  12 March 2014

J. Siekmann  and
P. Szabó
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
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 2 , June 1989 , pp. 402 - 414
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.)

References

REFERENCES

[AT 85]Arnborg, S. and Tidén, E., Unification problems with one-sided distributivity, Rewriting techniques and applications (Dijon, 1985), Lecture Notes in Computer Science, vol. 202, Springer-Verlag, Berlin, 1985, pp. 398–406.CrossRefGoogle Scholar
[Ba 86]Baader, F., Unification in varieties of idempotem semigroups, Semigroup Forum, vol. 36 (1987), pp. 127–145.CrossRefGoogle Scholar
[Bu 85]Buchberger, B., Basic features and development of the critical-pair/completion procedure, Rewriting techniques and applications (Dijon, 1985), Lecture Notes in Computer Science, vol. 202, Springer-Verlag, Berlin, 1985, pp. 1–45.CrossRefGoogle Scholar
[BS 81]Burris, S. and Sankappanavar, H. P., A course in universal algebra, Springer-Verlag, Berlin, 1981.CrossRefGoogle Scholar
[Da 73]Davis, M., Hilbert's tenth problem is unsolvable, American Mathematical Monthly, vol. 80 (1973), pp. 233–269.CrossRefGoogle Scholar
[FH 86]Fages, F. and Huet, G., Complete sets of unifiers and matchers in equational theories, Theoretical Computer Science, vol. 43 (1986), pp. 189–200.CrossRefGoogle Scholar
[Go 81]Goldfarb, W. D., The undecidability of the second-order unification problem, Theoretical Computer Science, vol. 13 (1981), pp. 225–230.CrossRefGoogle Scholar
[Gr 79]Grätzer, G., Universal algebra, Springer-Verlag, Berlin, 1979.CrossRefGoogle Scholar
[Hi 19]Hilbert, D., Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongress zu Paris 1900, Nachrichten von der Königl. Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-physikalische Klasse, 1900, pp. 253–297.Google Scholar
[Hm 64]Hmelevskij, J. I., The solution of certain systems of word equations, Doklady Akademii Nauk SSSR, vol. 156 (1964), pp. 749–751; English translation, Soviet Mathematics—Doklady, vol. 5 (1964), pp. 724–727.Google Scholar
[Hu 73]Huet, G., The undecidability of unification in third order logic, Information and Control, vol. 22 (1973), pp. 257–267.CrossRefGoogle Scholar
[Hu 80]Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, Journal of the Association for Computing Machinery, vol. 27 (1980), pp. 797–821.CrossRefGoogle Scholar
[HO 80]Huet, G. and Oppen, D. C., Equations and rewrite rules: a survey, Formal language theory (proceedings, Santa Barbara, California, 1979; Book, R. V., editor), Academic Press, New York, 1980, pp. 349–405.Google Scholar
[Ja 85]Jaffar, J., Minimal and complete word unification, Internal report, Monash University, Clayton, Victoria, Australia, 1985.Google Scholar
[KB 70]Knuth, D. E. and Bendix, P. B., Simple word problems in universal algebra, Computational problems in abstract algebra (proceedings, Oxford, 1967; Leech, J., editor), Academic Press, New York, 1970, pp. 263–297.Google Scholar
[Ki 89]Kirchner, J. C. (guest editor), Special issue on unification theory, Journal of Symbolic Computation (to appear).Google Scholar
[Ma 77]Makanin, G. S., The problem of solvability of equations in a free semigroup, Doklady Akademii Nauk SSSR, vol. 233 (1977), pp. 287–290; English translation, Soviet Mathematics—Doklady, vol. 18 (1977), pp. 330–334.Google Scholar
[Ma 70]Matiyasevich, Y., Enumerable sets are Diophantine, Doklady Akademii Nauk SSSR, vol. 191 (1970), pp. 279–282; English translation, Soviet Mathematic—Doklady, vol. 11 (1970), pp. 354–358.Google Scholar
[Mz 86]Mzali, J., Matching with distributivity, Eighth international conference on automated deduction (Oxford, 1986), Lecture Notes in Computer Science, vol. 230, Springer-Verlag, Berlin, 1986, pp. 496–505.CrossRefGoogle Scholar
[PI 72]Plotkin, G. D., Building-in equational theories, Machine intelligence, vol. 7 (Meltzer, B. and Michie, D., editors), Edinburgh University Press, Edinburgh, 1972, pp. 73–90.Google Scholar
[Ro 65]Robinson, J. A., A machine-oriented logic based on the resolution principle, Journal of the Association for Computing Machinery, vol. 12 (1965), pp. 23–41.CrossRefGoogle Scholar
[Sc 86]Schmidt-Schauß, M., Unification under associativity and idempotence is of type nullary, Journal of Automated Reasoning, vol. 2 (1986), pp. 277–281.CrossRefGoogle Scholar
[Si 86]Siekmann, J., Unification theory, paper presented at the European conference on artificial intelligence, Brighton, 1986; to appear in Journal of Symbolic Computation.Google Scholar
[Si 75]Siekmann, J., Stringunification, Memo, Essex University, Colchester, 1975.Google Scholar
[Sz 82]Szabó, P., Theory of first order unification, Thesis, University of Karlsruhe, Karlsruhe, 1982. (in German)Google Scholar
[WR 67]Wos, L., Robinson, G. A., Carson, D. F. and Shalla, L., The concept of demodulation in theorem proving, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 698–709.CrossRefGoogle Scholar