ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Bisimulations on Data Graphs
Autor/es:
SANTIAGO FIGUEIRA; SERGIO ABRIOLA; DIEGO FIGUEIRA; PABLO BARCELÓ
Revista:
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, THE
Editorial:
AI ACCESS FOUNDATION
Referencias:
Año: 2018 vol. 61 p. 171 - 213
ISSN:
1076-9757
Resumen:
Bisimulation provides structural conditions to characterize indistinguishability from an external observer between 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 non-locality allowed, and the class of models considered (graphs, DAGs, trees). In particular, this analysis yields a hierarchy of tractable fragments.