Edinburgh Research Explorer

Regular expressions for data words

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://linkinghub.elsevier.com/retrieve/pii/S0022000015000276
Original languageEnglish
Pages (from-to)1278-1297
Number of pages20
JournalJournal of Computer and System Sciences
Volume81
Issue number7
DOIs
Publication statusPublished - Nov 2015

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.

Download statistics

No data available

ID: 19959356