License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-33334
URL:

; ;

Parameterized Regular Expressions and Their Languages

pdf-format:


Abstract

We study regular expressions that use variables, or parameters, which are interpreted as alphabet letters. We consider two classes of languages denoted by such expressions: under the possibility semantics, a word belongs to the language if it is denoted by some regular expression obtained by replacing variables with letters; under the certainty semantics, the word must be denoted by every such expression. Such languages are regular, and we show that they naturally arise in several applications such as querying graph databases and program analysis. As the main contribution of the paper, we provide a complete characterization of the complexity of the main computational problems related to such languages: nonemptiness, universality, containment, membership, as well as the problem of constructing NFAs capturing such languages. We also look at the extension when domains of variables could be arbitrary regular languages, and show that under the certainty semantics, languages remain regular and the complexity of the main computational problems does not change.

BibTeX - Entry

@InProceedings{barcel_et_al:LIPIcs:2011:3333,
  author =	{Pablo Barcel{\'o} and Leonid Libkin and Juan L. Reutter},
  title =	{{Parameterized Regular Expressions and Their Languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{351--362},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3333},
  URN =		{urn:nbn:de:0030-drops-33334},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.351},
  annote =	{Keywords: Regular expressions, complexity, decision problems, regular languages}
}

Keywords: Regular expressions, complexity, decision problems, regular languages
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI