Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T15:27:39.836Z 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: [email protected])
LUIGI PALOPOLI
Affiliation:
DEIS, University of Calabria, Via P. Bucci 41C, 87036 Rende (CS), Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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
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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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