Abstract
Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs. hex-programs extend ASP with external atoms for accessing arbitrary external information. In this paper we study inconsistent ASP- and hex-programs, i.e., programs which do not possess answer sets, and introduce a novel notion of inconsistency reasons for characterizing their inconsistency depending on the input facts. This problem is mainly motivated by upcoming applications for optimizations of the evaluation algorithms for hex-programs. Further applications can be found in ASP debugging. We then analyze the complexity of reasoning problems related to the computation of such inconsistency reasons. Finally, we present a meta-programming encoding in disjunctive ASP which computes inconsistency reasons for given normal logic programs, and a basic procedural algorithm for computing inconsistency reasons for general hex-programs.
This research has been supported by the Austrian Science Fund (FWF) project P27730.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The distinction is mainly relevant for nonground programs, which we disregard in this paper.
- 2.
For ordinary \(\varPi \), these are Gelfond & Lifschitz’s answer sets.
References
Brain, M., Gebser, M., Pührer, J., Schaub, T., Tompits, H., Woltran, S.: Debugging ASP programs by means of ASP. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 31–43. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72200-7_5
Brain, M., Vos, M.D.: Debugging logic programs under the answer set semantics. In: Vos, M.D., Provetti, A. (eds.) Answer Set Programming, Advances in Theory and Implementation, Proceedings of the 3rd International ASP 2005 Workshop, Bath, UK, 27–29 September 2005, CEUR Workshop Proceedings, vol. 142. CEUR-WS.org (2005)
Eiter, T., Fink, M., Ianni, G., Krennwallner, T., Redl, C., Schüller, P.: A model building framework for answer set programming with external computations. Theor. Pract. Logic Program. 16(4), 418–464 (2016)
Eiter, T., Fink, M., Krennwallner, T., Redl, C., Schüller, P.: Efficient HEX-program evaluation based on unfounded sets. J. Artif. Intell. Res. 49, 269–321 (2014)
Eiter, T., Fink, M., Schüller, P., Weinzierl, A.: Finding explanations of inconsistency in multi-context systems. Artif. Intell. 216, 233–274 (2014)
Eiter, T., Fink, M., Stepanova, D.: Inconsistency management for description logic programs and beyond. In: Faber, W., Lembo, D. (eds.) RR 2013. LNCS, vol. 7994, pp. 1–3. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39666-3_1
Eiter, T., Gottlob, G., Leone, N.: Semantics and complexity of abduction from default theories. Artif. Intell. 90(12), 177–223 (1997)
Eiter, T., Polleres, A.: Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications. TPLP 6(1–2), 23–60 (2006)
Faber, W.: Unfounded sets for disjunctive logic programs with arbitrary aggregates. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 40–52. Springer, Heidelberg (2005). doi:10.1007/11546207_4
Gebser, M., Puehrer, J., Schaub, T., Tompits, H.: A meta-programming technique for debugging answer-set programs. In: Fox, D., Gomes, C.P. (eds.) AAAI-08/IAAI-08 Proceedings, pp. 448–453 (2008). http://publik.tuwien.ac.at/files/PubDat_167810.pdf
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3–4), 365–386 (1991)
Redl, C.: On equivalence and inconsistency of answer set programs with external sources. In: Proceedings of the Thirty-First AAAI Conference (AAAI 2017), San Francisco, California, USA. AAAI Press, February 2017
Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987)
Syrjänen, T.: Debugging inconsistent answer set programs. In: Proceedings of the 11th International Workshop on Non-Monotonic Reasoning, pp. 77–84. Lake District, May 2006
Acknowledgements
The author thanks Markus Bretterbauer, who developed a prototype implementation for computing inconsistency reasons as studied in this paper.
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
Redl, C. (2017). Explaining Inconsistency in Answer Set Programs and Extensions. In: Balduccini, M., Janhunen, T. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2017. Lecture Notes in Computer Science(), vol 10377. Springer, Cham. https://doi.org/10.1007/978-3-319-61660-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-61660-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61659-9
Online ISBN: 978-3-319-61660-5
eBook Packages: Computer ScienceComputer Science (R0)