×

Strong order equivalence. (English) Zbl 1105.68100

Summary: Recently, strong equivalence for Answer Set Programming has been studied intensively, and was shown to be beneficial for modular programming and automated optimization. In this paper we define the novel notion of strong order equivalence for logic programs with preferences (ordered logic programs). Based on this definition we give, for several semantics for preference handling, necessary and sufficient conditions for programs to be strongly order equivalent. These results allow us also to associate a so-called SOE structure to each ordered logic program, such that two ordered logic programs are strongly order equivalent if and only if their SOE structures coincide. We also present the relationships among the studied semantics with respect to strong order equivalence, which differs considerably from their relationships with respect to preferred answer sets. Furthermore, we study the computational complexity of several reasoning tasks associated to strong order equivalence. Finally, based on the obtained results, we present-for the first time-simplification methods for ordered logic programs.

MSC:

68T27 Logic in artificial intelligence
68T30 Knowledge representation
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)

Software:

GULP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balduccini, M., Gelfond, M.: Logic programs with consistency-restoring rules. In Doherty, P., McCarthy, J., M.-A., Williams (eds.) International Symposium on Logical Formalization of Commonsense Reasoning. AAAI 2003 Spring Symposium Series, March (2003) · Zbl 1079.68094
[2] Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge, Massachusetts (2002) · Zbl 1056.68139
[3] Bidoit, N., Froidevaux, C.: Negation by default and unstratifiable logic programs. Theor. Comp. Sci. 78, 85–112 (1991) · Zbl 0716.68075 · doi:10.1016/0304-3975(51)90004-7
[4] Brass, S., Dix, J.: Disjunctive semantics based upon partial and bottom-up evaluation. In: Sterling, L. (ed.) Proceedings of the 12th Int. Conf. on Logic Programming, pp. 199–213. Tokyo, June 1995, MIT Press, Cambridge, Massachusetts (1995)
[5] Brass, S., Dix, J.: Semantics of (disjunctive) logic programs based on partial evaluation. J. Log. Program. 40(1), 1–46 (1999) (Extended Abstract appeared as [4]) · Zbl 0946.68088 · doi:10.1016/S0743-1066(98)10030-4
[6] Brewka, G.: Logic programming with ordered disjunction. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-2002), pp. 100–105. AAAI Press, Edmonton, Canada (2002)
[7] Brewka, G., Eiter, T.: Preferred answer sets for extended logic programs. Artif. Intell. 109(1-2), 297–356 (1999) · Zbl 0916.68091 · doi:10.1016/S0004-3702(99)00015-6
[8] Brewka, G., Niemelä, I., Truszczyński, M.: Answer set optimization. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), pp. 867–872. Morgan Kaufmann, San Francisco, California (2003)
[9] Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3), 374–425 (2001) · doi:10.1145/502807.502810
[10] Delgrande, J.P., Schaub, T., Tompits, H.: A framework for compiling preferences in logic programs. Theory Pract. Logic Program. 3(2), 129–187 (March 2003) · Zbl 1105.68323 · doi:10.1017/S1471068402001539
[11] 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) · doi:10.1111/j.0824-7935.2004.00240.x
[12] Eiter, T., Fink, M.: Uniform equivalence of logic programs under the stable model semantics. In: Palamidessi, C. (ed.) Logic Programming, 19th International Conference, ICLP 2003. Lecture Notes in Computer Science, vol. 2916, pp. 224–238. Springer, Berlin Heidelberg New York (2003) · Zbl 1204.68052
[13] Eiter, T., Fink, M., Sabbatini, G., Tompits, H.: A generic approach for knowledge-based information site selection. In: Fensel, D., Giunchiglia, F., McGuiness, D., Williams, M.-A. (eds.) Proceedings Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-02), April 22-25, Toulouse, France, pp. 459–469. Morgan Kaufmann, 2002. Extended version Technical Report INFSYS RR-1843-02-09, TU Wien, 2002. · Zbl 1105.68325
[14] Eiter, T., Fink, M., Tompits, H., Woltran, S.: Simplifying logic programs under uniform and strong equivalence. In: Lifschitz, V., Niemelä, I (eds.) Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’04). Lecture Notes in Computer Science, vol. 2923, pp. 87–99. Springer, Berlin Heidelberg New York (2004) · Zbl 1122.68369
[15] Eiter, T., Fink, M., Tompits, H., Woltran, S.: Simplifying logic programs under uniform and strong equivalence. In: Lifschitz, V., Niemelä, I. (eds.) Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-7), number 2923 in Lecture Notes in AI (LNAI), pp. 87–99, Fort Lauderdale, Florida, USA, January 2004. Springer Berlin Heidelberg New York. · Zbl 1122.68369
[16] Eiter, T., Fink, M., Tompits, H., Woltran, S.: Strong and uniform equivalence in answer-set programming: Characterizations and complexity results for the non-ground case. In: Veloso, M.M., Kambhampati, S. (eds.) Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI’05), pp. 695–700. AAAI Press/The MIT Press, Menlo Park, California (2005)
[17] Eiter, T., Fink, M., Woltran, S.: Semantical characterizations and complexity of equivalences in answer set programming. ACM Trans. Comput. Logic (in press) · Zbl 1367.68031
[18] Faber, W., Konczak, K.: Strong equivalence for logic programs with preferences. In: Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 430–435, August 2005
[19] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Logic Programming: Proceedings Fifth Intl Conference and Symposium, pp. 1070–1080. The MIT Press, Cambridge, Massachusetts (1988)
[20] Inoue, K., Sakama, C.: Equivalence of logic programs under updates. In: Alferes, J., Leite, J. (eds.) Proceedings of the Ninth European Conference on Logics in Artificial Intelligence (JELIA’04). Lecture Notes in Computer Science, vol. 3229, pp. 174–186. Springer, Berlin Heidelberg New York (2004) · Zbl 1111.68381
[21] Inoue, K., Sakama, C.: Equivalence in abductive logic. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 472–477 (2005) · Zbl 1134.68480
[22] Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Trans. on Comput. Logic 2(4), 526–541 (2001) · Zbl 1365.68149 · doi:10.1145/383779.383783
[23] Lin, F.: Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Fensel, D., Giunchiglia, F., McGuiness, D., Williams, M.-A. (eds.) Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR’02), pp. 170–176. Morgan Kaufmann, San Francisco, California (2002)
[24] Lin, F., Chen, Y.: Discovering classes of strongly equivalent logic programs. In: Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 516–521, August 2005.
[25] Marek, V., Truszczyński, M.: Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm: a 25-Year Perspective, pp. 375–398. Springer, Berlin Heidelberg New York (1999) · Zbl 0979.68524
[26] Marek, V.W., Truszczyński, M.: Autoepistemic logic. J. ACM 38(3), 588–619 (1991) · Zbl 0799.68176 · doi:10.1145/116825.116836
[27] Niemelä, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25, 241–273 (1999) · Zbl 0940.68018 · doi:10.1023/A:1018930122475
[28] Osorio, M., Navarro, J.A., Arrazola, J.: Equivalence in answer set programming. In: Logic Based Program Synthesis and Transformation, 11th International Workshop (LOPSTR 2001). Lecture Notes in Computer Science, vol. 2372, pp. 57–75. Springer, Berlin Heidelberg New York (2001) · Zbl 1073.68586
[29] Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading, Massachusetts (1994) · Zbl 0833.68049
[30] Pearce, D., Valverde, A.: Some types of equivalence for logic programs and equilibrium logic. In: Proceedings of International Joint Conference on Declarative Programming, APPIA-GULP-PRODE 2003, pp. 350–361. Universitá degli Studi di Reggio Calabria (2003)
[31] plp. http://www.cs.uni-potsdam.de/\(\sim\)torsten/plp (2002)
[32] Sakama, C., Inoue, K.: Representing priorities in logic programs. In: Maher, M. (ed.) Proceedings of the Joint International Conference and Symposium on Logic Programming, pp. 82–96. The MIT Press, Cambridge, Massachusetts (1996)
[33] Schaub, T., Wang, K.: A semantic framework for preference handling in answer set programming. Theory Pract. Logic Program. 3(4–5), 569–607 (2003) · Zbl 1079.68016 · doi:10.1017/S1471068403001844
[34] Turner, H.: Strong equivalence made easy: nested expressions and weight constraints. Theory Pract. Logic Program. 3(4–5), 609–622 (2003) · Zbl 1079.68017 · doi:10.1017/S1471068403001819
[35] Wang, K., Zhou, L.: Comparisons and computation of well-founded semantics for disjunctive logic programs. ACM Trans. Comput. Logic 6(2), April (2005) · Zbl 1367.68042
[36] Wang, K., Zhou, L., Lin, F.: Alternating fixpoint theory for logic programs with priority. In: Computational Logic - CL 2000, First International Conference, Proceedings, number 1861 in Lecture Notes in AI (LNAI), pp. 164–178, London, UK, July 2000 Springer, Berlin Heidelberg New York (2000) · Zbl 0983.68025
[37] Woltran, S.: Characterizations for relativized notions of equivalence in answer set programming. In: Alferes, J., Leite, J. (eds.) Logics in Artificial Intelligence, 9th European Conference (JELIA 2004) Lecture Notes in Computer Science, vol. 3229, pp. 161–173. Springer, Berlin Heidelberg New York (2004) · Zbl 1111.68695
[38] Zhang, Y., Foo, N.: Answer sets for prioritized logic programs. In: Maluszynski, J. (ed.) Proceedings of the International Symposium on Logic Programming (ILPS-97), pp. 69–84. The MIT Press, Cambridge, Massachusetts (1997) · Zbl 0944.68017
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.