𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Simple second-order languages for which unification is undecidable

✍ Scribed by William M. Farmer

Book ID
104326073
Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
824 KB
Volume
87
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Farmer, W.M., Simple second-order languages for which unification is undecidable, Theoretical Computer Science 87 (1991) 25-41. We improve Goldfarb's Theorem on the undecidability of the second-order unification problem. More precisely, we prove that there is a natural number n such that the unification problem is undecidable for all second-order languages containing a binary function constant and at least n function variables with arity ~> 1. This result allows one to draw a sharp line between second-order languages for which unification is decidable and second-order languages for which unification is undecidable. It also answers a question raised by the k-provability problem that is not answered by Goldfarb's result. Our proof utilizes term rewriting concepts and several unification coding tricks.

πŸ“œ SIMILAR VOLUMES

A differential technique which is indepe
A differential technique which is independent of initial conditions for calculating the rate constant of a second-order reaction
✍ Walter Y. Wen πŸ“‚ Article πŸ“… 1973 πŸ› John Wiley and Sons 🌐 English βš– 340 KB πŸ‘ 1 views

## Abstract It has been shown that experimental errors of the initial conditions of a second‐order reaction can cause erroneous results with the rate constant calculated directly from the differential or integrated rate expression. By means of a computer method, a differential technique has been de