Three unpublished papers on loop detection in Prolog

The following three unpublished papers can be downloaded from here (the first two of them are written in 1992 jointly with Igor Durdanovic; the third one contains the slides of a talk at the 2011 Spring Conference of FMI):

Remark 1. In each of the present on-line versions of the first two papers, a footnote is omitted, namely one to the sentence on page 2 where the sequence τ0, τ1, τ2, … is introduced. In the first of the papers, the text of this footnote was:

“In a certain sense (to be explained elsewhere), there are some optimal choices of this sequence. One of them is the sequence 0, 1, 6, 29, 134, 613, 2798, 12765, 58230, 265621, … determined by means of the equalities τ0=0, τ1=1, τi+2=5τi+1−2τi+1 (this is an analog of a result from [1]).”

In the second paper, the footnote was the same, but with [2] instead of [1]. Unfortunately the intention to explain the optimality in question elsewhere was not carried out, and meanwhile the corresponding information was lost.

Remark 2. Due to lack of information at the time of writing the first two papers, the reference [1] in the first one and the reference [2] in the second one are to a paper published by the first author in 1987, whereas they ought to be to the earlier paper of F. E. Fich “Lower bounds for the cycle detection problem”, which appeared in 1983. Let us note that except for the above-mentioned footnotes nothing else in the papers relies on these references.

Last modification of this file: April 30, 2022