Abstract
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 language | English |
|---|---|
| Title of host publication | Logic Programming - 17th International Conference, ICLP 2001, Proceedings |
| Editors | Philippe Codognet |
| Pages | 197-211 |
| Number of pages | 15 |
| ISBN (Electronic) | 9783540429357 |
| DOIs | |
| State | Published - 2001 |
| Event | 17th International Conference on Logic Programming, ICLP 2001 - Paphos, Cyprus Duration: Nov 26 2001 → Dec 1 2001 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2237 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 17th International Conference on Logic Programming, ICLP 2001 |
|---|---|
| Country/Territory | Cyprus |
| City | Paphos |
| Period | 11/26/01 → 12/1/01 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2001.
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science