On Downward Closure Ordinals of Logic Programs

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 ${\{{\mathit{P}}_{\mathit{\alpha }}\}}_{\mathit{\alpha }\mathrm{<}{\mathit{ϵ}}_0}$ of logic programs where any member ${\mathit{P}}_{\mathit{\alpha }}$ has downward closure ordinal $\mathit{\omega }+\mathit{\alpha }$ .