Fixed-parameter complexity of semantics for logic programs

Zbigniew Lonc, Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


In the paper 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 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.

Original languageEnglish
Title of host publicationLogic Programming - 17th International Conference, ICLP 2001, Proceedings
EditorsPhilippe Codognet
Number of pages15
ISBN (Electronic)9783540429357
StatePublished - 2001
Event17th International Conference on Logic Programming, ICLP 2001 - Paphos, Cyprus
Duration: Nov 26 2001Dec 1 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th International Conference on Logic Programming, ICLP 2001

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Fixed-parameter complexity of semantics for logic programs'. Together they form a unique fingerprint.

Cite this