Paper Info
Title
Guarded open answer set programming
Abstract
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 (μ(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling a characterization of an answer set semantics by μLGF formulas. Finally, we relate guarded OASP to Datalog LITE, thus linking an answer set semantics to a semantics based on fixed point models of extended stratified Datalog programs. From this correspondence, we deduce 2-EXPTIME-completeness of satisfiability checking w.r.t. (loosely) guarded programs.
Year
DOI
Venue
2005
10.1007/11546207_8
LPNMR
Keywords
Field
DocType
fpl formula,guarded program,fixed point model,guarded fixed point logic,fpl translation,open answer,answer set programming,fixed point logic,answer set semantics,guarded open answer set,open answer set programming,satisfiability,generic programming,fixed point
Predicate transformer semantics,Discrete mathematics,Horn clause,Guarded logic,Computer science,Algorithm,Decidability,Theoretical computer science,Stable model semantics,Answer set programming,Datalog,Undecidable problem
Conference
Volume
ISSN
ISBN
3662
0302-9743
3-540-28538-5
Citations 
PageRank 
References 
14
0.75
14
Authors
3
Name
Order
Citations
PageRank
Stijn Heymans146337.60
Davy Van Nieuwenborgh223114.54
Dirk Vermeir369485.34