Computing large and small stable models

Details Computing large and small stable models Computing large and small stable models

2000-02-03

arxiv.org/abs/cs/0002001v2

Theory and Practice of Logic Programming, 2(1), pp. 2002

Computer Science

Logic in Computer Science

This paper is a full version of the conference paper of the same title that was published in the Proceedings of the 1999 Inter

Scientific paper

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(n^c), where 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].

Affiliated with

Also associated with

No associations

Rating

Computing large and small stable models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing large and small stable models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing large and small stable models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-232898