Description:
<jats:p>Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed-point logic (FPL) extension of Clark's completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (<jats:italic>loosely</jats:italic>)<jats:italic>guarded programs</jats:italic>. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed-point logic (μ(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling, for the first time, a characterization of an answer set semantics by μLGF formulas.</jats:p><jats:p>We further extend the open answer set semantics for programs with generalized literals. Such<jats:italic>generalized programs (gPs)</jats:italic>have interesting properties, for example, the ability to express infinity axioms. We restrict the syntax of gPs such that both rules and generalized literals are<jats:italic>guarded</jats:italic>. Via a translation to guarded fixed-point logic, we deduce 2-EXPTIME-completeness of satisfiability checking in such<jats:italic>guarded gPs</jats:italic>(GgPs).<jats:italic>Bound GgPs</jats:italic>are restricted GgPs with EXPTIME-complete satisfiability checking, but still sufficiently expressive to optimally simulate<jats:italic>computation tree logic</jats:italic>(CTL). We translate Datalog lite programs to GgPs, establishing equivalence of GgPs under an open answer set semantics, alternation-free μGF, and Datalog LITE.</jats:p>