NDLI: Computing Loops with at Most One External Support Rule

Content Provider	ACM Digital Library
Author	Chen, Xiaoping Ji, Jianmin Lin, Fangzhen
Copyright Year	2013
Abstract	A consequence of a logic program under answer set semantics is one that is true for all answer sets. This article considers using loop formulas to compute some of these consequences in order to increase the efficiency of answer set solvers. Since computing loop formulas are in general intractable, we consider only loops with either no external support or at most one external support, as their loop formulas are either unit or binary clauses. We show that for disjunctive logic programs, loop formulas of loops with no external support can be computed in polynomial time, and that an iterative procedure using unit propagation on these formulas and the program completion computes the well-founded models in the case of normal logic programs and the least fixed point of a simplification operator used by DLV for disjunctive logic programs. For loops with at most one external support, their loop formulas can be computed in polynomial time for normal logic programs, but are NP-hard for disjunctive programs. So for normal logic programs, we have a procedure similar to the iterative one for loops without any external support, but for disjunctive logic programs, we present a polynomial approximation algorithm. All these algorithms have been implemented, and our experiments show that for certain logic programs, the consequences computed by our algorithms can significantly speed up current ASP solvers cmodels, clasp, and DLV.
Starting Page	1
Ending Page	34
Page Count	34
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/2422085.2422088
Volume Number	14
Issue Number	1
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Answer set semantics Answer set solvers Disjunctive logic programs Loop formulas Normal logic programs Well-founded semantics
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

Computing Loops with at Most One External Support Rule for Disjunctive Logic Programs

Computing loops with at most one external support rule.

F.: Computing loops with at most one external support rule (2008)

Well-founded semantics for description logic programs in the semantic web

Computing Loops with at Most One External Support Rule for Disjunctive Logic Programs

Under consideration for publication in Theory and Practice of Logic Programming 1 Computing Loops with at Most One External Support Rule for Basic Logic Programs with Arbitrary Constraint Atoms (2003)

Comparisons and computation of well-founded semantics for disjunctive logic programs

Proceedings, Eleventh International Conference on Principles of Knowledge Representation and Reasoning (2008) Computing Loops with at Most One External Support Rule

A comparison of disjunctive well-founded semantics (2006).

Computing Loops with at Most One External Support Rule

Similar Documents

Computing Loops with at Most One External Support Rule for Disjunctive Logic Programs

Computing loops with at most one external support rule.

F.: Computing loops with at most one external support rule (2008)

Well-founded semantics for description logic programs in the semantic web

Computing Loops with at Most One External Support Rule for Disjunctive Logic Programs

Under consideration for publication in Theory and Practice of Logic Programming 1 Computing Loops with at Most One External Support Rule for Basic Logic Programs with Arbitrary Constraint Atoms (2003)

Comparisons and computation of well-founded semantics for disjunctive logic programs

Proceedings, Eleventh International Conference on Principles of Knowledge Representation and Reasoning (2008) Computing Loops with at Most One External Support Rule

A comparison of disjunctive well-founded semantics (2006).

Computing Loops with at Most One External Support Rule