The fixed points of logic programs with Herbrand base \({\mathbb{N}}\) (Q2639644)

A Herbrand base with signature \((a_ o,a_ 1,...,a_ k\); \(b_ o,b_ 1,...,b_ 1)\), where \(a_ i\), \(b_ j\in {\mathbb{N}}\), is considered. This base has \(a_ i\) predicate symbols of arity i(0\(\leq i\leq k)\) and \(b_ j\) functions of arity j(0\(\leq j\leq 1)\). Some results are given for logic programs with signature (of the underlying Herbrand base) (0,1; 1,1). Such programs use a unary predicate, a unary function symbol and a single constant. The Herbrand base is identified with \({\mathbb{N}}\) and interpretations are subsets of \({\mathbb{N}}\). For logic programs \(P=(C,R)\), with \(C\subseteq {\mathbb{N}}\) is an arbitrary set of constant rules and R is a finite non empty set of simple rules the program transformation \(T_ p\) and a transformation \(J_ p: 2^{{\mathbb{N}}}\to 2^{{\mathbb{N}}}\) are defined. It is proved that \(J_ p(L)\) is a fixed point of \(T_ p\) for an arbitrary set \(L\subseteq {\mathbb{N}}\) and that whenever C is regular, \(J_ p(L)\) is regular for an arbitrary set \(L\subseteq {\mathbb{N}}.\) Finally, a logic program P of signature (0,1; 1,1) is given, which satisfies the properties: P has a fixed point F of arbitrary recursive complexity and there is no finite, non-empty \(S\subseteq F\) such that F-S is a fixed point of P.