Abstract We investigate the expressive power of Higher-Order $Datalog^\neg$ under both the well-founded and the stable model semantics, establishing tight connections with complexity classes. We prove that under the well-founded semantics, for all $k\geq 1$ , $(k+1)$ -Order $Datalog^\neg$ captures $k-\textsf {EXP}$ , a result that holds without explicit ordering of the input database. The proof of this fact can be performed either by using the powerful existential predicate variables of the language or by using partially applied relations and relation enumeration. Furthermore, we demonstrate that this expressive power is retained within a stratified fragment of the language. Under the stable model semantics, we show that $(k+1)$ -Order $Datalog^\neg$ captures $\textsf {co}-(k-\textsf {NEXP})$ using cautious reasoning and $k-\textsf {NEXP}$ using brave reasoning, again with analogous results for the stratified fragment augmented with choice rules. Our results establish a hierarchy of expressive power, highlighting an interesting trade-off between order and non-determinism in the context of higher-order logic programing: increasing the order of programs under the well-founded semantics can surpass the expressive power of lower-order programs under the stable model semantics.

We extend the well-known representation theorem for interlaced bilattices to the broader class of weak interlaced bilattices. Based on this new theorem, we develop a fixpoint theory for non-monotone functions over weak infinitarily interlaced bilattices. Our theory generalizes classical fixpoint constructions introduced by Fitting, as-well-as recent results in the area of approximation fixpoint theory. We argue that the proposed theory has direct practical applications: we develop the semantics of higher-order logic programming with negation under an arbitrary weak infinitarily interlaced bilattice with negation, generalizing in this way recent work on the three-valued semantics of this formalism. We consider a line of research, initiated by Fitting, which investigates the structure of the consistent parts of bilattices in order to obtain natural generalizations of Kleene’s three-valued logic. We demonstrate that the consistent parts of bilattices are closely connected to weak bilattices, generalizing previous results of Fitting and Kondo.

Abstract We propose a stable model semantics for higher-order logic programs. Our semantics is developed using Approximation Fixpoint Theory (AFT), a powerful formalism that has successfully been used to give meaning to diverse non-monotonic formalisms. The proposed semantics generalizes the classical two-valued stable model semantics of Gelfond and Lifschitz as well as the three-valued one of Przymusinski, retaining their desirable properties. Due to the use of AFT, we also get for free alternative semantics for higher-order logic programs, namely supported model, Kripke-Kleene, and well-founded. Additionally, we define a broad class of stratified higher-order logic programs and demonstrate that they have a unique two-valued higher-order stable model which coincides with the well-founded semantics of such programs. We provide a number of examples in different application domains, which demonstrate that higher-order logic programming under the stable model semantics is a powerful and versatile formalism, which can potentially form the basis of novel ASP systems.