CONICET | Buscador de Institutos y Recursos Humanos

Bisimulation provides structural conditions to characterize indistinguishability from an external observerbetween nodes on labeled graphs. It is a fundamental notion used in many areas, such as verification, graph-structured databases, and constraint satisfaction.However, several current applications use graphs where nodes also contain data (the so called "data graphs´´), 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 logics like PDL with tests for data equality--- with and without transitive closure operators.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 (graphs, DAGs, trees). In particular, this analysis yields a hierarchy of tractable fragments.