Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/18447

Title: Regular expressions for data words
Authors: Libkin, Leonid
TAN, Tony
Vrgoc, Domagoj
Issue Date: 2015
Citation: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), p. 1278-1297
Abstract: In this paper we define and study regular expressions for data words. We first define regular expressions with memory (REM), which extend standard regular expressions with limited memory and show that they capture the class of data words defined by register automata. We also study the complexity of the standard decision problems for REM, which turn out to be the same as for register automata. In order to lower the complexity of main reasoning tasks, we then look at two natural subclasses of REM that can define many properties of interest in the applications of data words: regular expressions with binding (REWB) and regular expressions with equality (REWE). We study their expressive power and analyse the complexity of their standard decision problems. We also establish the following strict hierarchy of expressive power: REM is strictly stronger than REWB, and in turn REWB is strictly stronger than REWE.
URI: http://hdl.handle.net/1942/18447
DOI: 10.1016/j.jcss.2015.03.005
ISI #: 000356644600012
ISSN: 0022-0000
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
preprint323.71 kBAdobe PDF
published version569.71 kBAdobe PDF

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