AAAI Publications, Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Bisimulations on Data Graphs
Sergio Abriola, Pablo Barceló, Diego Figueira, Santiago Figueira

Last modified: 2016-03-30


Bisimulation provides structural conditions to characterize indistinguishability between nodes on graph-like structures from an external observer. It is a fundamental notion used in many areas. However, many applications use graphs where nodes have data, and where observers can test for equality or inequality of data values (e.g., asking the attribute "name" of a node to be different from that of all its neighbors). The present work constitutes a first investigation of "data aware"' bisimulations on data graphs. We study the problem of computing such bisimulations, based on the observational indistinguishability for XPath — a language that extends modal logic with tests for data equality. We show that in general the problem is pspace-complete, but identify several restrictions that yield better complexity bounds (coNP, ptime) by controlling suitable parameters of the problem; namely, the amount of em non-locality allowed, and the class of models considered (graph, DAG, tree). In particular, this analysis yields a hierarchy of tractable fragments.


complexity; XPath; data graphs; data trees; bisimulation

Full Text: PDF