×

zbMATH — the first resource for mathematics

Iteratively-supported formulas and strongly supported models for Kleene answer set programs (extended abstract). (English) Zbl 06658184
Michael, Loizos (ed.) et al., Logics in artificial intelligence. 15th European conference, JELIA 2016, Larnaca, Cyprus, November 9–11, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-48757-1/pbk; 978-3-319-48758-8/ebook). Lecture Notes in Computer Science 10021. Lecture Notes in Artificial Intelligence, 536-542 (2016).
Summary: In this extended abstract, we discuss the use of iteratively-supported formulas (ISFs) as a basis for computing strongly-supported models for Kleene answer set programs (\(\text{ASP}^{K}\)). \(\text{ASP}^{K}\) programs have a syntax identical to classical ASP programs. The semantics of \(\text{ASP}^{K}\) programs is based on the use of Kleene three-valued logic and strongly-supported models. For normal \(\text{ASP}^{K}\) programs, their strongly supported models are identical to classical answer sets using stable model semantics. For disjunctive \(\text{ASP}^{K}\) programs, the semantics weakens the minimality assumption resulting in a classical interpretation for disjunction. We use ISFs to characterize strongly-supported models and show that they are polynomially bounded.
For the entire collection see [Zbl 1350.68015].
MSC:
68T27 Logic in artificial intelligence
Software:
ASSAT; clasp; Cmodels
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chan, P.: A possible world semantics for disjunctive databases. IEEE Trans. Knowl. Data Eng. 5(2), 282–292 (1993) · Zbl 05108985 · doi:10.1109/69.219736
[2] Doherty, P., Szałas, A.: Stability, supportedness, minimality and kleene answer set programs. In: Eiter, T., Strass, H., Truszczyński, M., Woltran, S. (eds.) Advances in Knowledge Representation. LNCS, vol. 9060, pp. 125–140. Springer, Heidelberg (2015) · Zbl 1432.68457 · doi:10.1007/978-3-319-14726-0_9
[3] Ferraris, P., Lifschitz, V.: On the minimality of stable models. In: Balduccini, M., Son, T.C. (eds.) Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. LNCS, vol. 6565, pp. 64–73. Springer, Heidelberg (2011) · Zbl 1326.68056 · doi:10.1007/978-3-642-20832-4_5
[4] Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: a conflict-driven answer set solver. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 260–265. Springer, Heidelberg (2007) · Zbl 05211342 · doi:10.1007/978-3-540-72200-7_23
[5] Gelfond, M., Kahl, Y.: Knowledge Representation, Reasoning, and the Design of Intelligent Agents -The Answer-Set Programming Approach. Cambridge University Press, Cambridge (2014) · doi:10.1017/CBO9781139342124
[6] Lee, J., Lifschitz, V.: Loop formulas for disjunctive logic programs. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 451–465. Springer, Heidelberg (2003) · Zbl 1204.68056 · doi:10.1007/978-3-540-24599-5_31
[7] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7(3), 499–562 (2006) · Zbl 1367.68308 · doi:10.1145/1149114.1149117
[8] Lierler, Y.: cmodels – SAT-based disjunctive answer set solver. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 447–451. Springer, Heidelberg (2005) · doi:10.1007/11546207_44
[9] Lifschitz, V.: Thirteen definitions of a stable model. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol. 6300, pp. 488–503. Springer, Heidelberg (2010) · Zbl 1287.68021 · doi:10.1007/978-3-642-15025-8_24
[10] Lifschitz, V., Razborov, A.: Why are there so many loop formulas? ACM Trans. Comput. Log. 7(2), 261–268 (2006) · Zbl 1367.68036 · doi:10.1145/1131313.1131316
[11] Lin, F., Zhao, J.: On tight logic programs and yet another translation from normal logic programs to propositional logic. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the IJCAI-03, pp. 853–858. Morgan Kaufmann (2003)
[12] Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by SAT solvers. Artif. Intell. 157(1–2), 115–137 (2004) · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004
[13] Liu, G., Janhunen, T., Niemelä, I.: Answer set programming via mixed integer programming. In: Brewka, G., T., E., McIlraith, S. (eds.) Proceedings of the KR 2012. AAAI Press (2012)
[14] Pelov, N., Ternovska, E.: Reducing inductive definitions to propositional satisfiability. In: Gabbrielli, M., Gupta, G. (eds.) ICLP 2005. LNCS, vol. 3668, pp. 221–234. Springer, Heidelberg (2005) · Zbl 1165.68494 · doi:10.1007/11562931_18
[15] Sakama, C., Inoue, K.: An alternative approach to the semantics of disjunctive logic programs and deductive databases. J. Autom. Reasoning 13(1), 145–172 (1994) · Zbl 0819.68036 · doi:10.1007/BF00881915
[16] Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1–2), 181–234 (2002) · Zbl 0995.68021 · doi:10.1016/S0004-3702(02)00187-X
[17] Soininen, T., Niemelä, I.: Developing a declarative rule language for applications in product configuration. In: Gupta, G. (ed.) PADL 1999. LNCS, vol. 1551, pp. 305–319. Springer, Heidelberg (1999)
[18] Son, T., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming. TPLP 7(3), 355–375 (2007) · Zbl 1111.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.