Abstract
In answer-set programming (ASP), the main focus usually is on computing answer sets which correspond to solutions to the problem represented by a logic program. Simple reasoning over answer sets is sometimes supported by ASP systems (usually in the form of computing brave or cautious consequences), but slightly more involved reasoning problems require external postprocessing. Generally speaking, it is often desirable to use (a subset of) brave or cautious consequences of a program P 1 as input to another program P 2 in order to provide the desired solutions to the problem to be solved. In practice, the evaluation of the program P 1 currently has to be decoupled from the evaluation of P 2 using an intermediate step which collects the desired consequences of P 1 and provides them as input to P 2. In this work, we present a novel method for representing such a procedure within a single program, and thus within the realm of ASP itself. Our technique relies on rewriting P 1 into a so-called manifold program, which allows for accessing all desired consequences of P 1 within a single answer set. Then, this manifold program can be evaluated jointly with P 2 avoiding any intermediate computation step. For determining the consequences within the manifold program we use weak constraints, which is strongly motivated by complexity considerations. As applications, we present encodings for computing the ideal extension of an abstract argumentation framework and for computing world views of a particular class of epistemic specifications.
This work was supported by the Vienna Science and Technology Fund (WWTF), grant ICT08-028, and by M.I.U.R. within the Italia-Austria internazionalization project “Sistemi basati sulla logica per la rappresentazione di conoscenza: estensioni e tecniche di ottimizzazione” and the PRIN project LoDeN. A preliminary version of this paper appeared in the Proceedings of the the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), pp. 115–128, Springer LNAI 5753, 2009.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Marek, V.W., Truszczyński, M.: Stable models and an alternative logic programming paradigm. In: Apt, K., Marek, V.W., Truszczyński, M., Warren, D.S. (eds.) The Logic Programming Paradigm – A 25-Year Perspective, pp. 375–398. Springer, Heidelberg (1999)
Niemelä, I.: Logic programming with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3-4), 241–273 (1999)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge (2002)
Gelfond, M.: Representing knowledge in A-prolog. In: Kakas, A., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond. LNCS (LNAI), vol. 2408, pp. 413–451. Springer, Heidelberg (2002)
Balduccini, M., Gelfond, M., Watson, R., Nogueira, M.: The USA-advisor: A case study in answer set planning. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 439–442. Springer, Heidelberg (2001)
Leone, N., Gottlob, G., Rosati, R., Eiter, T., Faber, W., Fink, M., Greco, G., Ianni, G., Kałka, E., Lembo, D., Lenzerini, M., Lio, V., Nowicki, B., Ruzzi, M., Staniszkis, W., Terracina, G.: The INFOMIX System for advanced integration of incomplete and inconsistent data. In: Proceedings of the 24th ACM SIGMOD International Conference on Management of Data (SIGMOD 2005), pp. 915–917. ACM Press, New York (2005)
Soininen, T., Niemelä, I., Tiihonen, J., Sulonen, R.: Representing configuration knowledge with weight constraint rules. In: Provetti, A., Son, T.C. (eds.) Proceedings of the 1st International Workshop on Answer Set Programming (2001)
Gebser, M., Liu, L., Namasivayam, G., Neumann, A., Schaub, T., Truszczyński, M.: The first answer set programming system competition. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 3–17. Springer, Heidelberg (2007)
Bravo, L., Bertossi, L.E.: Logic programs for consistently querying data integration systems. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), pp. 10–15. Morgan Kaufmann, San Francisco (2003)
Saccà, D.: Multiple total stable models are definitely needed to solve unique solution problems. Inf. Process. Lett. 58(5), 249–254 (1996)
Buccafurri, F., Leone, N., Rullo, P.: Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12(5), 845–860 (2000)
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)
Reiter, R.: On closed world data bases. In: Gallaire, H., Minker, J. (eds.) Logic and Databases, pp. 55–76. Plenum Press, New York (1978)
Bench-Capon, T.J.M., Dunne, P.E.: Argumentation in artificial intelligence. Artif. Intell. 171(10-15), 619–641 (2007)
Dung, P.M., Mancarella, P., Toni, F.: Computing ideal sceptical argumentation. Artif. Intell. 171(10-15), 642–674 (2007)
Gelfond, M.: Logic programming and reasoning with incomplete information. Annals of Mathematics and Artificial Intelligence 12(1-2), 89–116 (1994)
Gelfond, M.: Strong introspection. In: Proceedings of the 9th National Conference on Artificial Intelligence (AAAI 1991), pp. 386–391. AAAI Press / The MIT Press (1991)
Wang, K., Zhang, Y.: Nested epistemic logic programs. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 279–290. Springer, Heidelberg (2005)
Zhang, Y.: Computational properties of epistemic logic programs. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), pp. 308–317. AAAI Press, Menlo Park (2006)
Zhang, Y.: Updating epistemic logic programs. J. Log. Comput. 19(2), 405–423 (2009)
Truszczyński, M.: Revisiting epistemic specifications. In: Balduccini, M., Son, T.C. (eds.) Gelfond Festschrift. LNCS (LNAI), vol. 6565, pp. 315–333. Springer, Heidelberg (2011)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Comput. 9(3/4), 365–386 (1991)
Egly, U., Gaggl, S.A., Woltran, S.: Answer-set programming encodings for argumentation frameworks. Argument and Computation 1(2), 144–177 (2010)
Dunne, P.E.: The computational complexity of ideal semantics. Artif. Intell. 173(18), 1559–1591 (2009)
Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–358 (1995)
Dunne, P.E.: Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell. 171(10-15), 701–729 (2007)
Osorio, M., Zepeda, C., Nieves, J.C., Cortés, U.: Inferring acceptable arguments with answer set programming. In: Proceedings of the 6th Mexican International Conference on Computer Science (ENC 2005), pp. 198–205. IEEE, Los Alamitos (2005)
Watson, R.: A splitting set theorem for epistemic specifications. In: Baral, C., Truszczyński, M. (eds.) Proceedings of the 8th International Workshop on Non-Monotonic Reasoning, NMR 2000 (2000), http://arxiv.org/abs/cs/0003038
Eiter, T., Veith, H.: On the complexity of data disjunctions. Theor. Comput. Sci. 288(1), 101–128 (2002)
Delgrande, J.P., Schaub, T.: Reasoning credulously and skeptically within a single extension. Journal of Applied Non-Classical Logics 12(2), 259–285 (2002)
Eiter, T., Faber, W., Leone, N., Pfeifer, G.: Computing preferred answer sets by meta-interpretation in answer set programming. TPLP 3(4-5), 463–498 (2003)
Faber, W., Woltran, S.: A framework for programming with module consequences. In: de Vos, M., Schaub, T. (eds.) Proceedings of the LPNMR 2009 Workshop on Software Engineering for Answer Set Programming, SEA 2009, pp. 34–48 (2009), http://sea09.cs.bath.ac.uk/downloads/sea09proceedings.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Faber, W., Woltran, S. (2011). Manifold Answer-Set Programs and Their Applications. In: Balduccini, M., Son, T.C. (eds) Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. Lecture Notes in Computer Science(), vol 6565. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20832-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-20832-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20831-7
Online ISBN: 978-3-642-20832-4
eBook Packages: Computer ScienceComputer Science (R0)