Paper Info
Title
Guarded open answer set programming with generalized literals
Abstract
We extend the open answer set semantics for programs with generalized literals. Such extended programs (EPs) have interesting properties, e.g. the ability to express infinity axioms – EPs that have but infinite answer sets. However, reasoning under the open answer set semantics, in particular satisfiability checking of a predicate w.r.t. a program, is already undecidable for programs without generalized literals. In order to regain decidability, we restrict the syntax of EPs such that both rules and generalized literals are guarded. Via a translation to guarded fixed point logic (μGF), in which satisfiability checking is 2-EXPTIME-complete, we deduce 2-EXPTIME-completeness of satisfiability checking in such guarded EPs (GEPs). Bound GEPs are restricted GEPs with EXPTIME-complete satisfiability checking, but still sufficiently expressive to optimally simulate computation tree logic (CTL). We translate Datalog LITE programs to GEPs, establishing equivalence of GEPs under an open answer set semantics, alternation-free μGF, and Datalog LITE. Finally, we discuss ω-restricted logic programs under an open answer set semantics.
Year
DOI
Venue
2006
10.1007/11663881_11
FoIKS
Keywords
Field
DocType
bound geps,computation tree logic,guarded fixed point logic,infinite answer set,guarded eps,open answer set semantics,particular satisfiability checking,satisfiability checking,guarded open answer set,exptime-complete satisfiability checking,generalized literal,satisfiability,fixed point
Computation tree logic,Guarded logic,Computer science,Axiom,Decidability,Theoretical computer science,Stable model semantics,Datalog,Answer set programming,Undecidable problem
Conference
Volume
ISSN
ISBN
3861
0302-9743
3-540-31782-1
Citations 
PageRank 
References 
3
0.41
15
Authors
3
Name
Order
Citations
PageRank
Stijn Heymans146337.60
Davy Van Nieuwenborgh223114.54
Dirk Vermeir369485.34