JFLP: Volume 1998, Article 4
The Journal of Functional and Logic Programming
Volume 1998
Article 4
Published by The MIT Press . Copyright 1998 Massachusetts Institute of Technology.
Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.
Heinz Faßbender and Sebastian Maneth
28 May 1998
Abstract
During the execution of functional logic programs, E -unification problems have to be solved quite frequently, where the underlying equational theory is induced by recursive functions. But, what about the decidability of those E -unification problems? Up to now, there does not exist a concrete answer to this question for classes of equational theories which are induced by particular recursive functions. In this paper, we try to give an answer to this question by drawing and verifying a strict border between undecidability and decidability of E -unification problems for particular classes of recursive functions. Since this result shows that the E -unification problem is undecidable even for a very restricted class of recursive functions, the nondeterministic implementations of those problems in functional logic programming languages are justified.The following versions of the article are available:
-
Preformatted versions of the article (compressed with
gzip)- DVI (gzip'ped 39 kb)
- PostScript (gzip'ped 194 kb)
- PDF (gzip'ped 277 kb; uncompressed 423 kb)
-
LaTeX
(
JFLP-A98-04.tex, gzip'ped 21 kb) -
BIBTeX
(
JFLP-A98-04.bib, gzip'ped 3 kb) -
Figure 2
(
j9804f2.eps, gzip'ped 1 kb) - Parameter settings for custom formatting ( cjropts.tex , 165 bytes)
Self citation
@article{jflp98-04,
author={Heinz Fa{\ss}bender and Sebastian Maneth},
title={A Strict Border for the Decidability of E-Unification
for Recursive Functions},
journal={Journal of Functional and Logic Programming},
volume={1998},
number={4},
publisher={The MIT Press},
month={May},
year={1998}
}
Main page