Computing large and small stable models

Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

In this paper, we focus on the problem of existence and computing of small and large stable models. We show that for every fixed integer k, there is a linear-time algorithm to decide the problem LSM (large stable models problem): does a logic program P have a stable model of size at least |P|-k? In contrast, we show that the problem SSM (small stable models problem) to decide whether a logic program P has a stable model of size at most k is much harder. We present two algorithms for this problem but their running time is given by polynomials of order depending on k. We show that the problem SSM is fixed-parameter intractable by demonstrating that it is W[2]-hard. This result implies that it is unlikely an algorithm exists to compute stable models of size at most k that would run in time O(mc), where m is the size of the program and c is a constant independent of k. We also provide an upper bound on the fixed-parameter complexity of the problem SSM by showing that it belongs to the class W[3].

Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalTheory and Practice of Logic Programming
Volume2
Issue number1
DOIs
StatePublished - Jan 2002

Keywords

  • Fixed-parameter complexity
  • Stable models

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Computing large and small stable models'. Together they form a unique fingerprint.

Cite this