Querying Data Graphs with Arithmetical Regular Expressions
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1088-1093.
Abstract
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. These features allow us to express a number of natural properties, while keeping the data complexity (with a query fixed) in non-deterministic logarithmic space. 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.
@inproceedings{ijcai2016p158,
title = {Querying Data Graphs with Arithmetical Regular Expressions},
author = {Grabon, Maciej and Michaliszyn, Jakub and Otop, Jan and Wieczorek, Piotr},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {1088--1093},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/158},
}
TY - CPAPER TI - Querying Data Graphs with Arithmetical Regular Expressions AU - Grabon, Maciej AU - Michaliszyn, Jakub AU - Otop, Jan AU - Wieczorek, Piotr T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 1088 EP - 1093 UR - https://ijcai.org/proceedings/2016/158 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
