NDLI: Fixed-parameter complexity of semantics for logic programs

Please wait, while we are loading the content...

Fixed-parameter complexity of semantics for logic programs

Content Provider	ACM Digital Library
Author	Truszczyński, Miroslaw Lonc, Zbigniew
Copyright Year	2003
Abstract	A decision problem is called $\textit{parameterized}$ if its input is a pair of strings. One of these strings is referred to as a $\textit{parameter}.$ The following problem is an example of a parameterized decision problem with $\textit{k}$ serving as a parameter: given a propositional logic program $\textit{P}$ and a nonnegative integer $\textit{k},$ decide whether $\textit{P}$ has a stable model of size no more than $\textit{k}.$ Parameterized problems that are NP-complete often become solvable in polynomial time if the parameter is fixed. The problem to decide whether a program $\textit{P}$ has a stable model of size no more than $\textit{k},$ where $\textit{k}$ is fixed and not a part of input, can be solved in time $O(mn^{k}),$ where $\textit{m}$ is the size of $\textit{P}$ and $\textit{n}$ is the number of atoms in $\textit{P}.$ Thus, this problem is in the class P. However, algorithms with the running time given by a polynomial of order $\textit{k}$ are not satisfactory even for relatively small values of $\textit{k}.The$ key question then is whether significantly better algorithms (with the degree of the polynomial not dependent on $\textit{k})$ exist. To tackle it, we use the framework of fixed-parameter complexity. We establish the fixed-parameter complexity for several parameterized decision problems involving models, supported models, and stable models of logic programs. We also establish the fixed-parameter complexity for variants of these problems resulting from restricting attention to definite Horn programs and to purely negative programs. Most of the problems considered in the paper have high fixed-parameter complexity. Thus, it is unlikely that fixing bounds on models (supported models, stable models) will lead to fast algorithms to decide the existence of such models.
Starting Page	91
Ending Page	119
Page Count	29
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/601775.601779
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Normal logic programs Fixed-parameter complexity Stable models Supported models
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

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

Strongly equivalent logic programs

Semantical characterizations and complexity of equivalences in answer set programming

Tableau Calculi for Logic Programs under Answer Set Semantics

Context semantics, linear logic, and computational complexity

Stable models and difference logic

Super logic programs

Computing Loops with at Most One External Support Rule

Logic programs with propositional connectives and aggregates

Fixed-parameter complexity of semantics for logic programs

Similar Documents

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

Strongly equivalent logic programs

Semantical characterizations and complexity of equivalences in answer set programming

Tableau Calculi for Logic Programs under Answer Set Semantics

Context semantics, linear logic, and computational complexity

Stable models and difference logic

Super logic programs

Computing Loops with at Most One External Support Rule

Logic programs with propositional connectives and aggregates

Fixed-parameter complexity of semantics for logic programs