Name
Abstract | ||
|---|---|---|
The Semi-Unification Problem (SUP) is a natural generalization of both first-order unification and matching. The problem arises in various branches of computer science and logic. Although several special cases of SUP are known to be decidable, the problem in general has been open for several years. We show that SUP in general is undecidable, by reducing what we call the "boundedness problem" of Turing machines to SUP. The undecidability of this boundedness problem is established by a technique developed in the mid-1960's to prove related results about Turing machines, |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1006/inco.1993.1003 | STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing |
Keywords | Field | DocType |
semi-unification problem | Post correspondence problem,Discrete mathematics,Super-recursive algorithm,Description number,Turing reduction,Turing machine,Non-deterministic Turing machine,Mathematics,Computational complexity theory,Undecidable problem | Journal |
Volume | Issue | ISSN |
102 | 1 | Information and Computation |
ISBN | Citations | PageRank |
0-89791-361-2 | 61 | 5.38 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. J. Kfoury | 1 | 461 | 47.34 |
| Jerzy Tiuryn | 2 | 229 | 22.79 |
| P. Urzyczyn | 3 | 200 | 18.28 |