Querying Data Graphs with Arithmetical Regular Expressions
Authors: Maciej Graboń, Jakub Michaliszyn, Jan Otop, Piotr Wieczorek
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a query language LARE for graphs whose edges are labelled by a finite alphabet and nodes store unbounded data values. LARE is based on a variant of regular expressions with memory. Queries of LARE can compare quantities of memorised graph nodes and their neighbourhoods. ... We establish an algorithm that works efficiently not only with LARE, but also with a wider language defined using effective relational conditions, another formalism we propose. ... The query answering problem for effective relational conditions is NL-complete. We provide a translation from LARE queries into effective relational conditions, which proves that the data complexity of the query answering problem for LARE queries is in NL. The combined complexity is PSPACE-complete. |
| Researcher Affiliation | Academia | Maciej Grabo n and Jakub Michaliszyn and Jan Otop and Piotr Wieczorek Institute of Computer Science, University of Wrocław |
| Pseudocode | No | The paper describes formalisms and examples of AREs but does not provide any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating the release of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not describe experiments with datasets, thus no information on public dataset availability for training is provided. |
| Dataset Splits | No | This is a theoretical paper and does not describe experiments, thus no information on dataset splits for validation is provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper and does not describe experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper and does not describe experiments, thus no experimental setup details like hyperparameters are provided. |