Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Querying Data Graphs with Arithmetical Regular Expressions
Authors: Maciej Graboń, Jakub Michaliszyn, Jan Otop, Piotr Wieczorek
IJCAI 2016 | Venue PDF | 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. |