---
title: "Querying Data Graphs with Arithmetical Regular Expressions"
authors:
  - "Maciej Grabon"
  - "Jakub Michaliszyn"
  - "Jan Otop"
  - "Piotr Wieczorek"
doi: ""
url: "https://ijcai.org/proceedings/2016/158"
pdf: "https://ijcai.org/proceedings/2016/0158.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "1088-1093"
track: ""
keywords:
---

# Querying Data Graphs with Arithmetical Regular Expressions

Maciej Grabon, Jakub Michaliszyn, Jan Otop, Piotr Wieczorek

*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.