Bisimulations on data graphs

SERGIO ABRIOLA; DIEGO FIGUEIRA; PABLO BARCELÓ; SANTIAGO FIGUEIRA

Conferencia; KR 2016, 15th International Conference on Principles of Knowledge Representation and Reasoning; 2016

AAAI

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 non-locality allowed, and the class of models considered (graph, DAG, tree). In particular, this analysis yields a hierarchy of tractable fragments.