On Downward Closure Ordinals of Logic Programs

Article type: Research Article

Authors: Bagai, Rajiv^a | Bezem, Marc^b | van Emden, M.H.^a

Affiliations: [a] Dept. of Computer Science, University of Victoria, Victoria, BC V8W 2Y2, Canada | [b] CWI, Kruislaan 413, 1098 SJ Amsterdam, Netherlands

Abstract: Blair has shown that for every ordinal up to and including the least non-recursive ordinal there exists a logic program having that ordinal as downward closure ordinal. However, given such an ordinal and Blair’s proof, it is not straightforward to find a corresponding logic program. In fact, in the literature only a few isolated, ad hoc, examples of logic programs with downward closure ordinal greater than w can be found. We contribute to bridging the gap between what is known abstractly and what is known concretely by showing the connection between some of the existing examples and the well-known concept of the order of a vertex in a graph. Using this connection as a basis, we construct a family {Pα}α<ϵ0 of logic programs where any member Pα has downward closure ordinal ω+α.

DOI: 10.3233/FI-1990-13107

Journal: Fundamenta Informaticae, vol. 13, no. 1, pp. 67-83, 1990