A Note on Occur-Check

Włodzimierz Drabent

Most known results on avoiding the occur-check are based on the notion of "not subject to occur-check" (NSTO). It means that unification is performed only on such pairs of atoms for which the occur-check never succeeds in any run of a nondeterministic unification algorithm. Here we show that this requirement is too strong. We show how to weaken it, and present some related sufficient conditions under which the occur-check may be safely omitted. We show examples for which the proposed approach provides more general results than the approaches based on well-moded and nicely moded programs (this includes cases to which the latter approaches are inapplicable).

In Andrea Formisano, Yanhong Annie Liu, Bart Bogaerts, Alex Brik, Veronica Dahl, Carmine Dodaro, Paul Fodor, Gian Luca Pozzato, Joost Vennekens and Neng-Fa Zhou: Proceedings 37th International Conference on Logic Programming (Technical Communications) (ICLP 2021), Porto (virtual event), 20-27th September 2021, Electronic Proceedings in Theoretical Computer Science 345, pp. 54–67.
Published: 17th September 2021.

ArXived at: https://dx.doi.org/10.4204/EPTCS.345.17 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org