NDLI: Open answer set programming with guarded programs

Content Provider	ACM Digital Library
Author	Nieuwenborgh, Davy Van Heymans, Stijn Vermeir, Dirk
Copyright Year	2008
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 $(\textit{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, for the first time, a characterization of an answer set semantics by μLGF formulas. We further extend the open answer set semantics for programs with generalized literals. Such generalized programs (gPs) 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 $\textit{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 μGF, and Datalog LITE.
Starting Page	1
Ending Page	53
Page Count	53
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/1380572.1380575
Volume Number	9
Issue Number	4
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-29
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Answer set programming Fixed-point logic Open domains
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Logic Computational Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Tableau Calculi for Logic Programs under Answer Set Semantics

Preferred First-Order Answer Set Programs

Coordination in answer set programming

Fuzzy Equilibrium Logic: Declarative Problem Solving in Continuous Domains

Strongly equivalent logic programs

FDNC: Decidable nonmonotonic disjunctive logic programs with function symbols

Logic programs with propositional connectives and aggregates

Computing Loops with at Most One External Support Rule

Formalizing Negotiations Using Logic Programming

Open answer set programming with guarded programs

Similar Documents

Tableau Calculi for Logic Programs under Answer Set Semantics

Preferred First-Order Answer Set Programs

Coordination in answer set programming

Fuzzy Equilibrium Logic: Declarative Problem Solving in Continuous Domains

Strongly equivalent logic programs

FDNC: Decidable nonmonotonic disjunctive logic programs with function symbols

Logic programs with propositional connectives and aggregates

Computing Loops with at Most One External Support Rule

Formalizing Negotiations Using Logic Programming

Open answer set programming with guarded programs