Abstract
We present a purely model-theoretic semantics for disjunctive logic programs with negation, building on the infinite-valued approach recently introduced for normal logic programs [9]. In particular, we show that every disjunctive logic program with negation has a non-empty set of minimal infinite-valued models. Moreover, we show that the infinite-valued semantics can be equivalently defined using Kripke models, allowing us to prove some properties of the new semantics more concisely. In particular, for programs without negation, the new approach collapses to the usual minimal model semantics, and when restricted to normal logic programs, it collapses to the well-founded semantics. Lastly, we show that every (propositional) program has a finite set of minimal infinite-valued models which can be identified by restricting attention to a finite subset of the truth values of the underlying logic.
Partially supported by the the CICyT project TIC-2003-9001-C02, and by the Greek General Secretariat for Research and Technology and the Spanish MEC under a joint project of Scientific and Technological collaboration between Greece and Spain.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alcantara, J., Damasio, C.V., Pereira, L.M.: A Well-Founded Semantics with Disjunction. In: Gabbrielli, M., Gupta, G. (eds.) ICLP 2005. LNCS, vol. 3668, pp. 341–355. Springer, Heidelberg (2005)
Brass, S., Dix, J.: Characterizations of the (disjunctive) Stable Semantics by Partial Evaluation. Journal of Logic Programming 32(3), 207–228 (1997)
Brass, S., Dix, J.: Characterizations of the Disjunctive Well-founded Semantics: Confluent Calculi and Iterated GCWA. Journal of Automated Reasoning 20(1), 143–165 (1998)
Cabalar, P., et al.: Analysing and Extending Well-Founded and Partial Stable Semantics using Partial Equilibrium Logic. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 346–360. Springer, Heidelberg (2006)
Galanaki, C., Rondogiannis, P., Wadge, W.W.: An Infinite-Game Semantics for Well-Founded Negation. Annals of Pure and Applied Logic (to appear) (2007)
Pearce, D.: Equilibrium Logic. Ann. Math & Artificial Int. 47, 3–41 (2006)
Przymusinski, T.: Well-founded and stationary models of logic programs. Annals of Mathematics and Artificial Intelligence 12, 141–187 (1994)
Przymusinski, T.: Static Semantics of Logic Programs. Annals of Mathematics and Artificial Intelligence 14(2-4), 323–357 (1995)
Rondogiannis, P., Wadge, W.W.: Minimum Model Semantics for Logic Programs with Negation-as-Failure. ACM Transactions on Computational Logic 6(2), 441–467 (2005)
van Gelder, A., Ross, K.A., Schlipf, J.S.: The Well-Founded Semantics for General Logic Programs. Journal of the ACM 38(3), 620–650 (1991)
Wang, K.: Argumentation-based Abduction in Disjunctive Logic Programming. Journal of Logic Programming 45(1-3), 105–141 (2000)
Wang, K., Zhou, L.: Comparisons and Computation of Well-Founded Semantics for Disjunctive Logic Programs. ACM Transactions on Computational Logic 6(2), 295–327 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Cabalar, P., Pearce, D., Rondogiannis, P., Wadge, W.W. (2007). A Purely Model-Theoretic Semantics for Disjunctive Logic Programs with Negation. In: Baral, C., Brewka, G., Schlipf, J. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2007. Lecture Notes in Computer Science(), vol 4483. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72200-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-72200-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72199-4
Online ISBN: 978-3-540-72200-7
eBook Packages: Computer ScienceComputer Science (R0)