[Back]

S. Woltran:
"Equivalence between Extended Datalog Programs. A Brief Survey";
in: "Datalog Reloaded", O. de Moor, G. Gottlob, T. Furche, A. Sellers (ed.); Springer, 2011, ISBN: 978-3-642-24205-2, 106 - 119.

This paper gives a brief overview about the research field on equivalences in Answer-Set Programming. More precisely, we are concerned here with disjunctive logic programs under the stable-model semantics. Such programs can be understood as extended datalog queries (i.e., datalog augmented by default negation and disjunction). In particular, we shall report on characterizations and
complexity results for the notions of strong and respectively uniform equivalence. Most notably, uniform equivalence becomes undecidable in the presence of default negation, while strong equivalence remains decidable for full disjunctive datalog. We also consider a restricted setting where the arity of predicates is bounded by a fixed constant.