Please use this identifier to cite or link to this item:
Title: Regular Expressions with Binding over Data Words for Querying Graph Databases
Authors: Libkin, Leonid
TAN, Tony 
Vrgoc, Domagoj
Issue Date: 2013
Source: Proceedings of the 17th International Conference on Developments in Language Theory
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 7907
Abstract: Data words assign to each position a letter from a nite alphabet and a data value from an in nite set. Introduced as an ab- straction 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 ex- pense of a quite unnatural and unintuitive binding mechanism for data values. Our goal is to introduce a natural extension of regular expres- sions with proper bindings for data values, similar to the notion of freeze quanti ers used in connection with temporal logics over data words, and to study both language-theoretic properties of the resulting class of lan- guages of data words, and their applications in querying graph databases.
Document URI:
ISBN: 978-3-642-38770-8
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
dlt2013_submission_38.pdf449.98 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 27, 2022


checked on May 27, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.