Bisimilarity, Datalog and Negation

Antoun Jacques Yaacoub


We extend the concept of bisimilarity relation between goals from positive datalog programs to stratified and restricted Datalog programs with negation.  The introduction of negation forced us to reconsider the search space and the semantics in order to guarantee and preserve the soundness and completeness results. We address the problem of deciding whether two given goals are bisimilar with respect to given programs. When the given programs are stratified or restricted with negation, this problem is decidable.

Full Text:



BALBIANI, P., AND YAACOUB, A. Deciding the bisimilarity relation between Datalog goals (regular paper). In European Conference on Logics in Artificial Intelligence (JELIA), Toulouse, 26/09/2012- 28/09/2012 (, septembre 2012), L. Fari ˜nas del Cerro, A. Herzig, and J. Mengin, Eds., Springer, pp. 67–79.

YAACOUB, A. Towards an information flow in logic programming. International Journal of Computer Science Issues (IJCSI) 9, 2 , 2012.

YAACOUB, A., AND AWADA, A. Inference Control On Information Flow In Logic Programming. International Journal of Computer Science: Theory and Application (IJCSTA), 2015, Vol. 3, Issue.: 1, p. 13-22.

YAACOUB, A. Flux de l’information en programmation logique Université Paul Sabatier - Toulouse III, thèse de doctorat, 2012.

YAACOUB, A. AWADA, A. AND KOBEISSI, H. Information Flow in Concurrent Logic Programming. British Journal of Mathematics & Computer Science, 2015, Vol. 5, Issue.: 3, p. 367-382

VAN GELDER, A., ROSS, K., AND SCHLIPF, J.S. Unfounded Sets and Well-Founded Semantics for General Logic Programs Proceedings of the 7th Symposium on Principles of Databases, 1988, pp. 221–230 ACM SIGACT-SIGMOD

GELFOND, M. AND LIFSCHITZ, V. The Stable Model Semantics for Logic Programming ,in: R. Kowalski, K. Bowen (Eds.), Proceedings of the 5th International Conference on Logic ProgrammingMIT Press, Cambridge, MA, 1988, pp. 1070–1080

PRZYMUSINSKI, T.C. On the Declarative Semantics of Deductive Databases and Logic Programs ,in: J. Minker (Ed.), Foundations of Deductive Databases and Logic ProgrammingMorgan Kaufmann, Los Altos, CA, 1987, pp. 193–216

KEMP, D.B. AND TOPOR, R.W. Completeness of a Top-Down Query Evaluation Procedure for Stratified Databases ,in: R. Kowalski, K. Bowen (Eds.), Proceedings of the 5th International Conference on Logic Programming MIT Press, Cambridge, MA, 1988, pp. 178–194

SEKI, H. AND ITOH, H. A Query Evaluation Method for Stratified Programs under the Extended CWA ,in: R.A. Kowalski, K.A. Bowen (Eds.), Proceedings of the 5th International Conference on Logic ProgrammingMIT Press, Cambridge, MA, 1988, pp. 195–211

PRZYMUSINSKI, T.C. On the Declarative and Procedural Semantics of Logic Programs J. Automated Reasoning, 5, 1989, pp. 167–205

Sangiorgi, D.: On the origins of bisimulation and coinduction. In: ACM Trans. Program. Lang. Syst., pp. 1–41. ACM, USA, 2009

STEFANO, C., AND GEORG, G., AND LETIZIA, T. What you always wanted to know about Datalog (and never dared to ask). Knowledge and Data Engineering, IEEE Transactions, 1989, Vol. 1, Issue.: 1, p. 146–166.

CLARK K.L. Negation as Failure ,in: H. Gallaire, J. Minker (Eds.), Logic and Data Bases, Plenum, New York, 1978, pp. 293–322

LLOYD, J.W. Foundations of Logic Programming, 2nd Edition. Springer, 1987.

ULLMAN, J. Principles of Databases and Knowledge base Systems, Volume I and II. Computer Science Press, 1988.

Bol, R.N., Apt, K.R., Klop, J.W.: An Analysis of Loop Checking Mechanisms for Logic Programs. In: Theoretical Computer Science, vol. 86, pp. 35–79, 1991


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.