Mostrar el registro sencillo del ítem
dc.contributor.author
Abriola, Sergio Alejandro
dc.contributor.author
Barceló, Pablo
dc.contributor.author
Figueira, Diego
dc.contributor.author
Figueira, Santiago
dc.date.available
2020-03-19T19:59:57Z
dc.date.issued
2018-01
dc.identifier.citation
Abriola, Sergio Alejandro; Barceló, Pablo; Figueira, Diego; Figueira, Santiago; Bisimulations on data graphs; AI Access Foundation; Journal of Artificial Intelligence Research; 61; 1-2018; 171-213
dc.identifier.issn
1076-9757
dc.identifier.uri
http://hdl.handle.net/11336/100351
dc.description.abstract
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 (CO- NP, 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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
AI Access Foundation
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Bisimulation
dc.subject
Complexity
dc.subject
Data graphs
dc.subject
XPath
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Bisimulations on data graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-12-16T19:09:57Z
dc.journal.volume
61
dc.journal.pagination
171-213
dc.journal.pais
Canadá
dc.description.fil
Fil: Abriola, Sergio Alejandro. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación En Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación En Ciencias de la Computacion; Argentina
dc.description.fil
Fil: Barceló, Pablo. Universidad de Chile; Chile
dc.description.fil
Fil: Figueira, Diego. Centre National de la Recherche Scientifique; Francia
dc.description.fil
Fil: Figueira, Santiago. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación En Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación En Ciencias de la Computacion; Argentina
dc.journal.title
Journal of Artificial Intelligence Research
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://jair.org/index.php/jair/article/view/11174
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1613/jair.5637
Archivos asociados