\input zb-basic
\input zb-ioport
\iteman{io-port 06061695}
\itemau{Woltran, Stefan}
\itemti{Equivalence between extended datalog programs -- a brief survey.}
\itemso{de Moor, Oege (ed.) et al., Datalog reloaded. First international workshop, Datalog 2010, Oxford, UK, March 16--19, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-24205-2/pbk). Lecture Notes in Computer Science 6702, 106-119 (2011).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-24206-9\_7}
\end