×

Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions. (English) Zbl 1316.68036

Summary: Although answer set programming (ASP) is a powerful framework for declarative problem solving, it cannot in an intuitive way handle situations in which some rules are uncertain, or in which it is more important to satisfy some constraints than others. Possibilistic ASP (PASP) is a natural extension of ASP in which certainty weights are associated with each rule. In this paper we contrast two different views on interpreting the weights attached to rules. Under the first view, weights reflect the certainty with which we can conclude the head of a rule when its body is satisfied. Under the second view, weights reflect the certainty that a given rule restricts the considered epistemic states of an agent in a valid way, i.e. it is the certainty that the rule itself is correct. The first view gives rise to a set of weighted answer sets, whereas the second view gives rise to a weighted set of classical answer sets.

MSC:

68N17 Logic programming
68T37 Reasoning under uncertainty in the context of artificial intelligence

Software:

Potassco; Smodels
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, Y., Epistemic reasoning in logic programs, (Proceedings of the 20th International Joint Conference on Artifical Intelligence. Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAIʼ07 (2007)), 647-652
[2] Bauters, K.; Schockaert, S.; De Cock, M.; Vermeir, D., Weak and strong disjunction in possibilistic ASP, (Proceedings of the 5th International Conference on Scalable Uncertainty Management. Proceedings of the 5th International Conference on Scalable Uncertainty Management, SUMʼ11 (2011)), 475-488
[3] Nicolas, P.; Garcia, L.; Stéphan, I.; Lefèvre, C., Possibilistic uncertainty handling for answer set programming, Ann. Math. Artif. Intell., 47, 1-2, 139-181 (2006) · Zbl 1105.68104
[4] Bauters, K.; Schockaert, S.; De Cock, M.; Vermeir, D., Possibilistic answer set programming revisited, (Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, UAIʼ10 (2010)), 48-55
[5] Bauters, K.; Schockaert, S.; De Cock, M.; Vermeir, D., Possible and necessary answer sets of possibilistic answer set programs, (Proceedings of the 24th International Conference on Tools with Artificial Intelligence. Proceedings of the 24th International Conference on Tools with Artificial Intelligence, ICTAI (2012)), 836-843
[6] Gelfond, M.; Lifzchitz, V., The stable model semantics for logic programming, (Proceedings of the 5th Joint International Conference and Symposium on Logic Programming. Proceedings of the 5th Joint International Conference and Symposium on Logic Programming, ICLPʼ88 (1988)), 1081-1086
[7] Baral, C., Knowledge, Representation, Reasoning and Declarative Problem Solving (2003), Cambridge University Press · Zbl 1056.68139
[8] Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3 (1994), Oxford University Press), 439-513
[9] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[10] Janhunen, T., Representing normal programs with clauses, (Proceedings of the 16th Eureopean Conference on Artificial Intelligence. Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAIʼ04 (2004)), 358-362
[11] Lin, F.; Zhao, J., On tight logic programs and yet another translation from normal logic programs to propositional logic, (Proceedings of the 18th International Joint Conference on Artificial Intelligence. Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAIʼ03 (2003)), 853-858
[12] Niemelä, I.; Simons, P., Smodels - an implementation of the stable model and well-founded semantics for normal logic programs, (Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning. Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMRʼ97. Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning. Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMRʼ97, Lect. Notes Comput. Sci., vol. 1265 (1997)), 420-429
[13] Eiter, T.; Gottlob, G.; Leone, N., Abduction from logic programs: Semantics and complexity, Theor. Comput. Sci., 189, 1-2, 129-177 (1997) · Zbl 0893.68022
[14] Eiter, T.; Faber, W.; Leone, N.; Pfeifer, G.; Polleres, A., Planning under incomplete knowledge, (Proceedings of the First International Conference on Computational Logic. Proceedings of the First International Conference on Computational Logic, CLʼ2000 (2000)), 807-821 · Zbl 0983.68539
[15] Eiter, T.; Faber, W.; Leone, N.; Pfeifer, G.; Polleres, A., A logic programming approach to knowledge-state planning: Semantics and complexity, ACM Trans. Comput. Log., 5, 2, 206-263 (2004) · Zbl 1367.68301
[16] Dubois, D.; Lang, J.; Prade, H., Towards possibilistic logic programming, (Proceedings of the 8th Joint International Conference and Symposium on Logic Programming. Proceedings of the 8th Joint International Conference and Symposium on Logic Programming, ICLPʼ91 (1991)), 581-595
[17] Wagner, G., Negation in fuzzy and possibilistic logic programs, (Proceedings of the 2nd International Workshop on Logic Programming and Soft Computing. Proceedings of the 2nd International Workshop on Logic Programming and Soft Computing, LPSCʼ98 (1998)), 113-128
[18] Dubois, D.; Prade, H., Can we enforce full compositionality in uncertainty calculi?, (Proceedings of the 12th National Conference on Artificial Intelligence. Proceedings of the 12th National Conference on Artificial Intelligence, AAAIʼ94 (1994)), 149-154
[19] Chesñevar, C.; Simari, G.; Alsinet, T.; Godo, L., A logic programming framework for possibilistic argumentation with vague knowledge, (Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAIʼ04 (2004)), 76-84
[20] Amgoud, L.; Prade, H., Reaching agreement through argumentation: A possibilistic approach, (Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning, KRʼ04 (2004)), 175-182
[21] Nieves, J. C.; Osorio, M.; Cortés, U., Semantics for possibilistic disjunctive programs, (Proceedings of the 9th International Workshop on Logic Programming and Non-monotonic Reasoning. Proceedings of the 9th International Workshop on Logic Programming and Non-monotonic Reasoning, LPNMRʼ07 (2007)), 315-320 · Zbl 1149.68337
[22] Dubois, D.; Prade, H.; Schockaert, S., Stable models in generalized possibilistic logic, (Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KRʼ12 (2012)), 519-529
[23] Confalonieri, R.; Nieves, J. C.; Vázquez-Salceda, J., Pstable semantics for logic programs with possibilistic ordered disjunction, (Proceedings of the 11th International Conference on Advances in Artificial Intelligence. Proceedings of the 11th International Conference on Advances in Artificial Intelligence, AI*IAʼ09 (2009)), 52-61
[24] Osorio, M.; Pérez, J. A.N.; Ramírez, J. R.A.; Macías, V. B., Logics with common weak completions, J. Log. Comput., 16, 6, 867-890 (2006) · Zbl 1116.03022
[25] Nilsson, N. J., Probabilistic logic, Artif. Intell., 28, 1, 71-87 (1986) · Zbl 0589.03007
[26] Lukasiewicz, T., Probabilistic default reasoning with conditional constraints, Ann. Math. Artif. Intell., 34, 1-3, 35-88 (2002) · Zbl 1002.68175
[27] Dubois, D.; Prade, H.; Sandri, S., On possibility/probability transformations, (Proceedings of the 10th International Fuzzy Systems Association World Congress (1993)), 103-112
[28] Ng, R.; Subrahmanian, V., Stable model semantics for probabilistic deductive databases, (Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems. Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, ISMISʼ91. Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems. Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, ISMISʼ91, Lect. Notes Comput. Sci., vol. 542 (1991)), 162-171
[29] Baral, C.; Gelfond, M.; Rushton, N., Probabilistic reasoning with answer sets, Theory Pract. Log. Program., 9, 1, 57-144 (2009) · Zbl 1170.68003
[31] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 1-2, 107-136 (2006) · Zbl 1470.68221
[32] Mills, E., Uncertainty and price theory, Q. J. Econ., 73, 1, 116-130 (1959)
[33] Sandmo, A., On the theory of the competitive firm under price uncertainty, Am. Econ. Rev., 61, 1, 65-73 (1971)
[34] Garvey, P., Probability Methods for Cost Uncertainty Analysis: A Systems Engineering Perspective (2000), Taylor & Francis · Zbl 1006.91508
[35] Van Nieuwenborgh, D.; Vermeir, D., Preferred answer sets for ordered logic programs, (Proceeings of the European Conference on Logics in Artificial Intelligence. Proceeings of the European Conference on Logics in Artificial Intelligence, JELIA 2002, Cosenza, Italy. Proceeings of the European Conference on Logics in Artificial Intelligence. Proceeings of the European Conference on Logics in Artificial Intelligence, JELIA 2002, Cosenza, Italy, Lect. Notes Comput. Sci., vol. 2424 (2002)), 432-443 · Zbl 1013.68062
[36] Delgrande, J. P.; Schaub, T.; Tompits, H.; Wang, K., A classification and survey of preference handling approaches in nonmonotonic reasoning, Comput. Intell., 20, 2, 308-334 (2004)
[37] Buccafurri, F.; Leone, N.; Rullo, P., Strong and weak constraints in disjunctive datalog, (Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning. Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMRʼ97 (1997)), 2-17
[38] Gebser, M.; Pührer, J.; Schaub, T.; Tompits, H., A meta-programming technique for debugging answer-set programs, (Proceedings of the 23rd National Conference on Artificial Intelligence. Proceedings of the 23rd National Conference on Artificial Intelligence, AAAIʼ08 (2008)), 448-453
[39] Balduccini, M.; Gelfond, M., Logic programs with consistency-restoring rules, (International Symposium on Logical Formalization of Commonsense Reasoning. International Symposium on Logical Formalization of Commonsense Reasoning, AAAI 2003 Spring Symposium Series (2003)), 9-18
[40] 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
[41] Gebser, M.; Kaufmann, B.; Kaminski, R.; Ostrowski, M.; Schaub, T.; Schneider, M., Potassco: The Potsdam answer set solving collection, AI Commun., 24, 107-124 (2011) · Zbl 1215.68214
[42] Dubois, D.; Prade, H., Fuzzy relation equations and causal reasoning, Fuzzy Sets Syst., 75, 2, 119-134 (1995) · Zbl 0861.94041
[43] Medina, J.; Ojeda-Aciego, M.; Vojtáš, P., A multi-adjoint logic approach to abductive reasoning, (Proceedings of the 17th International Conference on Logic Programming. Proceedings of the 17th International Conference on Logic Programming, ICLPʼ01 (2001)), 269-283 · Zbl 1053.68707
[44] Ferraris, P.; Giunchiglia, E., Planning as satisfiability in nondeterministic domains, (Proceedings of the Seventeenth National Conference on Artificial Intelligence. Proceedings of the Seventeenth National Conference on Artificial Intelligence, AAAIʼ00 (2000)), 748-753
[45] Cimatti, A.; Roveri, M., Conformant planning via symbolic model checking and heuristic search, Artif. Intell., 159, 1-2, 127-206 (2004) · Zbl 1086.68591
[46] Hoffmann, J.; Brafman, R., Conformant planning via heuristic forward search: A new approach, Artif. Intell., 170, 6-7, 507-541 (2006) · Zbl 1131.68525
[47] Nieuwenborgh, D. V.; De Cock, M.; Vermeir, D., Fuzzy answer set programming, (Proceedings of the 10th European Conference on Logics in Artificial Intelligence. Proceedings of the 10th European Conference on Logics in Artificial Intelligence, JELIAʼ06. Proceedings of the 10th European Conference on Logics in Artificial Intelligence. Proceedings of the 10th European Conference on Logics in Artificial Intelligence, JELIAʼ06, Lect. Notes Comput. Sci., vol. 4160 (2006)), 359-372 · Zbl 1152.68619
[48] Janssen, J.; Schockaert, S.; Vermeir, D.; De Cock, M., A core language for fuzzy answer set programming, Int. J. Approx. Reason., 53, 4, 660-692 (2012) · Zbl 1246.68203
[49] Schockaert, S.; Janssen, J.; Vermeir, D., Fuzzy equilibrium logic: Declarative problem solving in continuous domains, ACM Trans. Comput. Log., 13, 4, 33:1-33:39 (2012) · Zbl 1351.68270
[50] Blondeel, M.; Schockaert, S.; De Cock, M.; Vermeir, D., NP-completeness of fuzzy answer set programming under Lukasiewicz semantics, (Proceedings of the 1st Workshop on Weighted Logics for Artificial Intelligence. Proceedings of the 1st Workshop on Weighted Logics for Artificial Intelligence, ECAIʼ12 (2012)), 43-50
[51] Damásio, C. V.; Pereira, L. M., Antitonic logic programs, (Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning. Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMRʼ01. Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning. Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMRʼ01, Lect. Notes Comput. Sci. (2001)), 379-392 · Zbl 1007.68022
[52] Alviano, M.; Naloza, R. P., Fuzzy answer sets approximations, (Proceedings of the 29th International Conference on Logic Programming. Proceedings of the 29th International Conference on Logic Programming, ICLPʼ13 (2013))
[53] Bouchon-Meunier, B.; Dubois, D.; Godo, L.; Prade, H., Fuzzy sets and possibility theory in approximate and plausible reasoning, (Fuzzy Sets in Approximate Reasoning and Information Systems. Fuzzy Sets in Approximate Reasoning and Information Systems, Handb. Fuzzy Sets Ser., vol. 5 (1999), Springer US), 15-190 · Zbl 0954.03027
[54] Bauters, K.; Schockaert, S.; De Cock, M.; Vermeir, D., Towards possibilistic fuzzy answer set programming, (Proceedings of the 13th International Workshop on Non-monotonic Reasoning. Proceedings of the 13th International Workshop on Non-monotonic Reasoning, NMR (2010))
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.