Parameterized regular expressions and their languages
Parameterized regular expressions and their languages
复制标题
DOI：
10.1016/j.tcs.2012.12.036
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
P. Barceló;Juan L. Reutter;L. Libkin
中科院分区：
文献类型：
--
作者：
P. Barceló;Juan L. Reutter;L. Libkin
我们研究使用变量或参数的正则表达式，这些变量或参数被解释为字母。我们考虑两类语言表示这样的表达式：根据可能性语义，一个词属于语言，如果它是由一些正则表达式表示通过替换变量与字母;确定性语义下，这个词必须表示的每一个这样的表达式。这样的语言是经常的，我们表明，他们自然出现在几个应用程序，如查询图形数据库和程序分析。作为本文的主要贡献，我们提供了一个完整的表征的复杂性的主要计算问题相关的语言：nonempiry，普遍性，包容性，成员资格，以及构建NFA捕获这些语言的问题。我们还研究了当变量的域可以是任意正则语言时的扩展，并表明在确定性语义下，语言仍然是正则的，主要计算问题的复杂性没有改变。
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.