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 | Source: | 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. | Keywords: | data words; register automata; regular expressions | Document URI: | http://hdl.handle.net/1942/18447 | ISSN: | 0022-0000 | e-ISSN: | 1090-2724 | DOI: | 10.1016/j.jcss.2015.03.005 | ISI #: | 000356644600012 | Rights: | © 2015 Elsevier Inc. All rights reserved. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
artikel 1.pdf | Non Peer-reviewed author version | 323.71 kB | Adobe PDF | View/Open |
1-s2.0-S0022000015000276-main.pdf Restricted Access | Published version | 569.71 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
13
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
20
checked on Sep 28, 2024
Page view(s)
50
checked on Sep 7, 2022
Download(s)
114
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.