ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
capítulos de libros
Título:
Bisimulations on Data Graphs
Autor/es:
SERGIO ABRIOLA; PABLO BARCELÓ; DIEGO FIGUEIRA; SANTIAGO FIGUEIRA
Libro:
Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference
Editorial:
AAAI Press
Referencias:
Lugar: Palo Alto, California; Año: 2016; p. 309 - 318
Resumen:
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 in- distinguishability 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 restric- tions that yield better complexity bounds (CO-NP, PTIME) by controlling suitable parameters of the problem; namely, the amount of non-locality allowed, and the class of mod- els considered (graph, DAG, tree). In particular, this analysis yields a hierarchy of tractable fragments.