Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations

G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

Motivated by applications in databases, this article considers various fragments of the calculus of binary relations. The fragments are obtained by leaving out, or keeping in, some of the standard operators, along with some derived operators such as set difference, projection, coprojection and residuation. For each considered fragment, a characterization is obtained for when two given binary relational structures are indistinguishable by expressions in that fragment. The characterizations are based on appropriately adapted notions of simulation and bisimulation. Keywords: Calculus of relations; indistinguishability; bisimulation; simulation; coprojection; residuation.
Original languageEnglish
Pages (from-to)549-580
JournalJournal of Logic and Computation
Volume25
Issue number3
DOIs
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations'. Together they form a unique fingerprint.

Cite this