Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T21:34:44.396Z Has data issue: false hasContentIssue false
  • English
  • Français

On the complexity of identifying head-elementary-set-free programs

Published online by Cambridge University Press:  13 November 2009

FABIO FASSETTI  and
LUIGI PALOPOLI
FABIO FASSETTI
Affiliation:
ICAR/CNR, Via P. Bucci 41C, 87036 Rende (CS), Italy (e-mail: f.fassetti@deis.unical.it)
LUIGI PALOPOLI
Affiliation:
DEIS, University of Calabria, Via P. Bucci 41C, 87036 Rende (CS), Italy (e-mail: palopoli@deis.unical.it)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Head-elementary-set-free (HEF) programs were proposed in (Gebser et al. 2007) and shown to generalize over head-cycle-free programs while retaining their nice properties. It was left as an open problem in (Gebser et al. 2007) to establish the complexity of identifying HEF programs. This note solves the open problem by showing that the problem is complete for coNP.

Keywords

computational complexityelementary setdisjunctive logic programhead-elementary-set-free program

Information

Type
Technical Note
Information
Theory and Practice of Logic Programming , Volume 10 , Issue 1 , January 2010 , pp. 113 - 123
Copyright
Copyright © Cambridge University Press 2009

References

Ben-Eliyahu, R. and Dechter, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, 1–2, 53–87.CrossRefGoogle Scholar
Ben-Eliyahu-Zohary, R. and Palopoli, L. 1997. Reasoning with minimal models: Efficient algorithms and applications. Artificial Intelligence 96, 2, 421–449.CrossRefGoogle Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374–425.CrossRefGoogle Scholar
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.Google Scholar
Gebser, M., Lee, J. and Lierler, Y. 2006. Elementary sets for logic programs. In Proc. of the 21st National Conference on Artificial Intelligence (AAAI). AAAI Press, 244–249.Google Scholar
Gebser, M., Lee, J. and Lierler, Y. 2007. Head-elementary-set-free logic programs. In Proc. of 9th International conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), Baral, C., Brewka, G., and Schlipfs, J. S., Eds. vol. 4483. Springer, 149–161.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of 5th International Conference and Symposium, Kowalski, R. A. and Bowen, K., Eds. MIT Press, 1070–1080.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The dlv system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.CrossRefGoogle Scholar