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

DOI10.1093/LOGCOM/EXU018zbMATH Open1331.68070arXiv1210.2688OpenAlexW2162834483MaRDI QIDQ5262475FDOQ5262475

Dirk Leinders, Stijn Vansummeren, Marc Gyssens, Jan Van den Bussche, D. Van Gucht, George H. L. Fletcher

Publication date: 15 July 2015

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

Abstract: Motivated by applications in databases, this paper 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.

Full work available at URL: https://arxiv.org/abs/1210.2688

Recommendations

• Bisimulations on Data Graphs
• Similarity measures for relational databases
• scientific article; zbMATH DE number 3936551
• Relational and Kleene-Algebraic Methods in Computer Science
• On similarity relations in fuzzy relational databases

zbMATH Keywords

simulationbisimulationcalculus of relationsindistinguishabilityresiduationcoprojection

Mathematics Subject Classification ID

Database theory (68P15) Cylindric and polyadic algebras; relation algebras (03G15)

Cited In (4)

• Model theory of XPath on data trees. II: Binary bisimulation and definability
• Structural characterizations of the navigational expressiveness of relation algebras on a tree
• Title not available (Why is that?)
• Relative expressive power of navigational querying on graphs

This page was built for publication: Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262475)