Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-07-04
Computer Science
Formal Languages and Automata Theory
Scientific paper
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 certainly 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.
Barceló Pablo
Libkin Leonid
Reutter Juan
No associations
LandOfFree
Parameterized Regular Expressions and their Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Regular Expressions and their Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Regular Expressions and their Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-3699