Open Answer Set Programming with Guarded Programs
  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 (loosely) guarded programs. 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 (mu(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
muLGF formulas. We further extend the open answer set semantics for programs
with generalized literals. Such generalized programs (gPs) have interesting
properties, e.g., the ability to express infinity axioms. We restrict the
syntax of gPs such that both rules and generalized literals are guarded. Via a
translation to guarded fixed point logic, we deduce 2-exptime-completeness of
satisfiability checking in such guarded gPs (GgPs). Bound GgPs are restricted
GgPs with exptime-complete satisfiability checking, but still sufficiently
expressive to optimally simulate computation tree logic (CTL). We translate
Datalog lite programs to GgPs, establishing equivalence of GgPs under an open
answer set semantics, alternation-free muGF, and Datalog lite.
