Bisimulations on Data Graphs
Authors: Sergio Abriola, Pablo Barceló, Diego Figueira, Santiago Figueira
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is an in-depth study of the complexity of computing data-aware bisimulations by fine-tuning on the level of non-locality allowed. This non-locality is measured in terms of (a) the lengths of the paths considered in the definition of bisimulation, and (b) the classes of models over which bisimulations are computed. In particular, we show the following: In full generality, checking whether two data graphs are data-aware bisimilar is PSPACE-complete. This is obtained by showing that the problem is polynomially equivalent to equivalence of nondeterministic finite automata, which is PSPACE-complete (Meyer & Stockmeyer, 1972). |
| Researcher Affiliation | Academia | Sergio Abriola EMAIL Universidad de Buenos Aires & ICC-CONICET Pablo Barcel o EMAIL Center for Semantic Web Research & DCC, University of Chile Diego Figueira EMAIL CNRS, La BRI, France Santiago Figueira EMAIL Universidad de Buenos Aires & ICC-CONICET |
| Pseudocode | No | The paper describes algorithms in prose, such as the 'standard greatest fixed point algorithm' mentioned in the proof of Proposition 14, but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code, nor does it include links to code repositories or mentions of code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis of bisimulations on 'data graphs'. It does not describe any specific datasets used for empirical evaluation, nor does it provide concrete access information for any publicly available datasets. Example 1 uses a conceptual 'movie database' for illustration, not as a real dataset for experiments. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments using specific datasets, therefore, it does not provide any information regarding dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setups. Consequently, no specific hardware details (like GPU/CPU models or processor types) used for running experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct practical experiments that would require specific software dependencies with version numbers for replication. It mentions 'XPath=' as a language but not as a software component used in an experimental setup. |
| Experiment Setup | No | The paper is theoretical and focuses on the complexity of bisimulations, rather than empirical evaluation. Therefore, it does not provide details about experimental setups, hyperparameters, or training configurations. |