TY - GEN
T1 - Fixed-parameter complexity of semantics for logic programs
AU - Lonc, Zbigniew
AU - Truszczyński, Mirosław
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84937243062
UR - https://www.scopus.com/pages/publications/84937243062#tab=citedBy
U2 - 10.1007/3-540-45635-x_21
DO - 10.1007/3-540-45635-x_21
M3 - Conference contribution
AN - SCOPUS:84937243062
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 197
EP - 211
BT - Logic Programming - 17th International Conference, ICLP 2001, Proceedings
A2 - Codognet, Philippe
T2 - 17th International Conference on Logic Programming, ICLP 2001
Y2 - 26 November 2001 through 1 December 2001
ER -