Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18447
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Libkin, Leonid | - |
dc.contributor.author | TAN, Tony | - |
dc.contributor.author | Vrgoc, Domagoj | - |
dc.date.accessioned | 2015-03-26T09:00:01Z | - |
dc.date.available | 2015-03-26T09:00:01Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), p. 1278-1297 | - |
dc.identifier.issn | 0022-0000 | - |
dc.identifier.uri | http://hdl.handle.net/1942/18447 | - |
dc.description.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. | - |
dc.description.sponsorship | The authors would like to thank the reviewers for their comments. This work was partially supported by the EPSRC Grants G049165 and J015377. Tan is also supported by FWO Pegasus Marie Curie fellowship and Vrgoc by the Millennium Nucleus Center for Semantic Web Research Grant NC120004. | - |
dc.language.iso | en | - |
dc.rights | © 2015 Elsevier Inc. All rights reserved. | - |
dc.subject.other | data words; register automata; regular expressions | - |
dc.title | Regular expressions for data words | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 1297 | - |
dc.identifier.issue | 7 | - |
dc.identifier.spage | 1278 | - |
dc.identifier.volume | 81 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.1016/j.jcss.2015.03.005 | - |
dc.identifier.isi | 000356644600012 | - |
item.fullcitation | Libkin, Leonid; TAN, Tony & Vrgoc, Domagoj (2015) Regular expressions for data words. In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), p. 1278-1297. | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2016 | - |
item.contributor | Libkin, Leonid | - |
item.contributor | TAN, Tony | - |
item.contributor | Vrgoc, Domagoj | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0022-0000 | - |
crisitem.journal.eissn | 1090-2724 | - |
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.