×

Deciding the bisimilarity relation between Datalog goals. (English) Zbl 1361.68029

Fariñas 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).
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.
For the entire collection see [Zbl 1246.68063].

MSC:

68N17 Logic programming
68P15 Database theory

Software:

Datalog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bol, R.N.: Loop Checking in Partial Deduction. J. Logic Programming 16, 25–46 (1993) · Zbl 0780.68012 · doi:10.1016/0743-1066(93)90022-9
[2] Bol, R.N., Apt, K.R., Klop, J.W.: An Analysis of Loop Checking Mechanisms for Logic Programs. Theoretical Computer Science 86, 35–79 (1991) · Zbl 0741.68027 · doi:10.1016/0304-3975(91)90004-L
[3] Devienne, P., Lebégue, P., Routier, J.-C.: Halting Problem of One Binary Horn Clause is Undecidable. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol. 665, pp. 48–57. Springer, Heidelberg (1993) · Zbl 0797.68057 · doi:10.1007/3-540-56503-5_7
[4] Gabbrielli, M., Levi, G., Meo, M.C.: Observable Behaviors and Equivalences of Logic Programs 122, 1–29 (1992) · Zbl 0834.68010
[5] Harland, J.: On Normal Forms and Equivalence for Logic Programs. In: Proceedings of the Joint International Conference and Symposium on Logic Programming, pp. 146–160 (1992)
[6] Hennessy, M., Milner, R.: On Observing Nondeterminism and Concurrency. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 299–309. Springer, Heidelberg (1980) · Zbl 0441.68018 · doi:10.1007/3-540-10003-2_79
[7] Hoare, C.A.R.: Communicating sequential processes. Commun. ACM 21, 666–677 (1978) · Zbl 0383.68028 · doi:10.1145/359576.359585
[8] Lifschitz, V., Pearce, D., Valverde, A.: Strongly Equivalent Logic Programs. ACM Transactions on Computational Logic (2000) · Zbl 1365.68149
[9] Lloyd, J.W.: Foundations in Logic Programming. Springer (1984) · Zbl 0547.68005 · doi:10.1007/978-3-642-96826-6
[10] Maher, M.: Equivalences of Logic Programs. In: Shapiro, E. (ed.) ICLP 1986. LNCS, vol. 225, pp. 410–424. Springer, Heidelberg (1986) · Zbl 0594.68011 · doi:10.1007/3-540-16492-8_91
[11] Milner, R.: Calculi for synchrony and asynchrony. Theoretical Computer Science 25, 267–310 (1983) · Zbl 0512.68026 · doi:10.1016/0304-3975(83)90114-7
[12] Park, D.: Concurrency and Automata on Infinite Sequences. In: Proceedings of the 5th GI-Conference on Theoretical Computer Science, pp. 167–183. Springer, UK (1981) · doi:10.1007/BFb0017309
[13] Sangiorgi, D.: On the origins of bisimulation and coinduction. In: ACM Trans. Program. Lang. Syst., pp. 1–41. ACM, USA (2009) · Zbl 1285.68112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.