\input zb-basic
\input zb-ioport
\iteman{io-port 06084933}
\itemau{Balbiani, Philippe; Yaacoub, Antoun}
\itemti{Deciding the bisimilarity relation between Datalog goals.}
\itemso{Fari\~nas del Cerro, Luis (ed.) et al., Logics in artificial intelligence. 13th European conference, JELIA 2012, Toulouse, France, September 26--28, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33352-1/pbk). Lecture Notes in Computer Science 7519. Lecture Notes in Artificial Intelligence, 67-79 (2012).}
\itemab
Summary: We introduce the concept of bisimulation between Datalog goals: two Datalog goals are bisimilar with respect to a given Datalog program when their SLD-trees, considered as relational structures, are bisimilar. We address the problem of deciding whether two given goals are bisimilar with respect to given programs. When the given programs are hierarchical or restricted, this problem is decidable in 2EXPTIME.
\itemrv{~}
\itemcc{}
\itemut{logic programming; Datalog; equivalence of goals; bisimulation; decision method; computational complexity}
\itemli{doi:10.1007/978-3-642-33353-8\_6}
\end