Regular expressions for data words

作者：

Highlights：

• Several classes of regular expressions for defining data word languages are introduced.

• We show what is needed to capture the notion of regularity over data words.

• We give a detailed overview of closure properties for introduced classes.

• We study the complexity of main reasoning tasks for introduced classes.

摘要

•Several classes of regular expressions for defining data word languages are introduced.•We show what is needed to capture the notion of regularity over data words.•We give a detailed overview of closure properties for introduced classes.•We study the complexity of main reasoning tasks for introduced classes.

论文关键词：Data words,Register automata,Regular expressions

论文评审过程：Received 2 May 2014, Revised 27 October 2014, Accepted 3 March 2015, Available online 24 March 2015, Version of Record 10 June 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.03.005