dc.creator | Barceló Baeza, Pablo | |
dc.creator | Reutter, Juan | |
dc.creator | Libkin, Leonid | |
dc.date.accessioned | 2014-03-06T20:09:15Z | |
dc.date.available | 2014-03-06T20:09:15Z | |
dc.date.created | 2014-03-06T20:09:15Z | |
dc.date.issued | 2013 | |
dc.identifier | Theoretical Computer Science 474 (2013) 21–45 | |
dc.identifier | doi:10.1016/j.tcs.2012.12.036 | |
dc.identifier | https://repositorio.uchile.cl/handle/2250/126425 | |
dc.description.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. | |
dc.language | en | |
dc.publisher | Elsevier | |
dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | |
dc.subject | Regular expressions with variables | |
dc.title | Parameterized regular expressions and their languages | |
dc.type | Artículo de revista | |