Open answer set programming with guarded programs

DOI10.1145/1380572.1380575MaRDI QIDQ5277815zbMATH OpenOpenAlexFDO

Authors Stijn Heymans, Davy Van Nieuwenborgh, Dirk Vermeir

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0603025

zbMATH Keywords

answer set programmingfixed-point logicopen domains

Mathematics Subject Classification ID

Logic programming (68N17)

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 (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.

Recommendations

• Logic Programming and Nonmonotonic Reasoning
• Foundations of Information and Knowledge Systems
• Conceptual logic programs
• Guarded resolution for answer set programming
• Open answer set programming for the semantic web

Cited in

(8)

• Guarded resolution for answer set programming
• Quantified Equilibrium Logic and Foundations for Answer Set Programs
• Synonymous theories and knowledge representations in answer set programming
• Conceptual logic programs
• Foundations of Information and Knowledge Systems
• Reasoning with forest logic programs using fully enriched automata
• Reasoning with forest logic programs and f-hybrid knowledge bases
• Logic Programming and Nonmonotonic Reasoning

This page was built for publication: Open answer set programming with guarded programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277815)