Abstract
We analyse alternative extensions of stable models for non-disjunctive logic programs with arbitrary Boolean formulas in the body, and examine two semantic properties. The first property, we call atom definability, allows one to replace any expression in rule bodies by an auxiliary atom defined by a single rule. The second property, well-supportedness, was introduced by Fages and dictates that it must be possible to establish a derivation ordering for all true atoms in a stable model so that self-supportedness is not allowed. We start from a generic fixpoint definition for well-supportedness that deals with: (1) a monotonic basis, for which we consider the whole range of intermediate logics; and (2), an assumption function, that determines which type of negated formulas can be added as defaults. Assuming that we take the strongest underlying logic in such a case, we show that only Equilibrium Logic satisfies both atom definability and strict well-suportedness.
Partially supported by Xunta de Galicia (projects GPC ED431B 2016/035 and 2016-2019 ED431G/01 for CITIC center) and ERDF; by the Centre International de Mathématiques et d’Informatique de Toulouse (CIMI), contract ANR-11-LABEX-0040-CIMI within program ANR-11-IDEX-0002-02; by UPM RP151046021 and by Spanish MINECO project TIN2015-70266-C2-1-P.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
- 1.
We allow the exception \(\varphi \rightarrow \bot \) since, as we will see later, this corresponds to \(\lnot \varphi \) in intermediate logics.
- 2.
Many other properties of Equilibrium Logic, studied elsewhere, also speak in its favour, e.g. not least the characterisation of strong equivalence, [6].
References
Gelfond, M., Lifschitz, V.: The stable models semantics for logic programming. In: Proceedings of the 5th International Conference on Logic Programming, pp. 1070–1080 (1988)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9, 365–385 (1991)
Inoue, K., Sakama, C.: Negation as failure in the head. J. Log. Program. 35(1), 39–78 (1998)
Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Ann. Math. Artif. Intell. 25, 369–389 (1999)
Pearce, D.: A new logical characterisation of stable models and answer sets. In: Dix, J., Pereira, L.M., Przymusinski, T.C. (eds.) NMELP 1996. LNCS, vol. 1216, pp. 57–70. Springer, Heidelberg (1997). doi:10.1007/BFb0023801
Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Trans. Comput. Log. 2(4), 526–541 (2001)
Ferraris, P.: Answer sets for propositional theories. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS, vol. 3662, pp. 119–131. Springer, Heidelberg (2005). doi:10.1007/11546207_10
Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs: semantics and complexity. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS, vol. 3229, pp. 200–212. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30227-8_19
Truszczyński, M.: Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. Artif. Intell. 174(16), 1285–1306 (2010)
Shen, Y.D., Wang, K., Eiter, T., Fink, M., Redl, C., Krennwallner, T., Deng, J.: FLP answer set semantics without circular justifications for general logic programs. Artif. Intell. 213, 1–41 (2014)
Fages, F.: Consistency of Clark’s completion and existence of stable models. J. Methods Log. Comput. Sci. 1(1), 51–60 (1994)
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Ricca, F., Schaub, T.: ASP-Core-2 input language format (2013). https://www.mat.unical.it/aspcomp2013/ASPStandardization
Eiter, T., Tompits, H., Woltran, S.: On solution correspondences in answer-set programming. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005), Edinburgh, Scotland, UK, pp. 97–102. Professional Book Center (2005)
Aguado, F., Cabalar, P., Fandinno, J., Pearce, D., Pérez, G., Vidal, C.: Forgetting auxiliary atoms in forks. In: Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2017) (2017)
Clark, K.L.: Negation as failure. In: Gallaire, H., Minker, J. (eds.) Logic and Databases, pp. 293–322. Plenum Press, New York (1978)
McDermott, D.V., Doyle, J.: Non-monotonic logic I. Artif. Intell. 13(1–2), 41–72 (1980)
Tasharrofi, S.: A rational extension of stable model semantics to the full propositional language. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI 2013, pp. 1118–1124. AAAI Press (2013)
Alviano, M., Faber, W.: Stable model semantics of abstract dialectical frameworks revisited: a logic programming perspective. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 2684–2690 (2015)
Acknowledgements
We are very thankful to the anonymous reviewers for their helpful comments and suggestions to improve the paper, especially for pointing out example after Theorem 1 which led to a more accurate reformulation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Cabalar, P., Fandinno, J., Fariñas, L., Pearce, D., Valverde, A. (2017). On the Properties of Atom Definability and Well-Supportedness in Logic Programming. In: Oliveira, E., Gama, J., Vale, Z., Lopes Cardoso, H. (eds) Progress in Artificial Intelligence. EPIA 2017. Lecture Notes in Computer Science(), vol 10423. Springer, Cham. https://doi.org/10.1007/978-3-319-65340-2_51
Download citation
DOI: https://doi.org/10.1007/978-3-319-65340-2_51
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-65339-6
Online ISBN: 978-3-319-65340-2
eBook Packages: Computer ScienceComputer Science (R0)