Regular Expressions with Binding over Data Words for Querying Graph Databases

Leonid Libkin, Tony Tan, Domagoj Vrgoc

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Data words assign to each position a letter from a finite alphabet and a data value from an infinite set. Introduced as an abstraction of paths in XML documents, they recently found applications in querying graph databases as well. Those are actively studied due to applications in such diverse areas as social networks, semantic web, and biological databases. Querying formalisms for graph databases are based on specifying paths conforming to some regular conditions, which led to a study of regular expressions for data words.

Previously studied regular expressions for data words were either rather limited, or had the full expressiveness of register automata, at the expense of a quite unnatural and unintuitive binding mechanism for data values. Our goal is to introduce a natural extension of regular expressions with proper bindings for data values, similar to the notion of freeze quantifiers used in connection with temporal logics over data words, and to study both language-theoretic properties of the resulting class of languages of data words, and their applications in querying graph databases.
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings
PublisherSpringer-Verlag GmbH
Number of pages13
ISBN (Electronic)978-3-642-38771-5
ISBN (Print)978-3-642-38770-8
Publication statusPublished - 2013


Dive into the research topics of 'Regular Expressions with Binding over Data Words for Querying Graph Databases'. Together they form a unique fingerprint.

Cite this