Semantical Characterizations and Complexity of Equivalences in Answer Set Programming

Preprint English OPEN
Eiter, Thomas; Fink, Michael; Woltran, Stefan;
(2005)
  • Subject: Computer Science - Artificial Intelligence | Computer Science - Computational Complexity | F.4.1 | I.2.4 | I.2.3

In recent research on non-monotonic logic programming, repeatedly strong equivalence of logic programs P and Q has been considered, which holds if the programs P union R and Q union R have the same answer sets for any other program R. This property strengthens equivalen... View more
  • References (31)
    31 references, page 1 of 4

    [1] J. J. Alferes, J. A. Leite, L. M. Pereira, H. Przymusinska, and T. C. Przymusinski. Dynamic Updates of NonMonotonic Knowledge Bases. Journal of Logic Programming, 45(1-3):43-70, 2000.

    [2] C. Anger, K. Konczak, and T. Linke. NoMoRe: A System for Non-Monotonic Reasoning. In T. Eiter, W. Faber, and M. Truszczyn´ski, editors, Logic Programming and Nonmonotonic Reasoning - 6th International Conference, LPNMR'01, Vienna, Austria, September 2001, Proceedings, number 2173 in Lecture Notes in AI (LNAI), pages 406-410. Springer Verlag, September 2001.

    [3] D. Barrington, N. Immerman, and H. Straubing. On uniformity within N C1. Journal of Computer and System Sciences, 41:274-306, 1990.

    [4] R. Ben-Eliyahu and R. Dechter. Propositional Semantics for Disjunctive Logic Programs. Annals of Mathematics and Artificial Intelligence, 12:53-87, 1994.

    [5] W. Buntine. Generalised Subsumption and its Applications to Induction and Redundancy. Artificial Intelligence, 36(2):149-176, 1988.

    [6] S. Buss. The boolean formula value problem is in alogtime. In 19th Annual ACM Symposium on Theory of Computing, pages 123-131, 1987.

    [7] P. Cabalar. A Three-Valued Characterization for Strong Equivalence of Logic Programs. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI 2002), pages 106-111. AAAI Press/MIT Press, 2002.

    [8] M. Cadoli and M. Lenzerini. The Complexity of Propositional Closed World Reasoning and Circumscription. Journal of Computer and System Sciences, 48(2):255-310, Apr. 1994.

    [9] S. Chaudhuri and M. Y. Vardi. On the Equivalence of Recursive and Nonrecursive Datalog Programs. In Proceedings of the 11th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS 1992), pages 55-66. ACM, 1992.

    [10] S. Cosmadakis and P. Kanellakis. Parallel Evaluation of Recursive Rule Queries. In Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS 1986), pages 280-293. ACM, 1986.

  • Related Organizations (1)
  • Metrics
Share - Bookmark