

Author: Câmpeanu Cezar
Publisher: Springer Publishing Company
ISSN: 0001-5903
Source: Acta Informatica, Vol.46, Iss.3, 2009-05, pp. : 193-207
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
In this paper we address a standing question on pattern expressions (PE), namely whether the family of PE languages is closed under the intersection with regular languages. Since this family is not closed under complement, but is closed under reversal, another natural question has frequently been raised in the recent years, on whether particular languages such as the mirror language and the language of palindromes are PE languages. We give answers to these and other related questions as well, thus providing an insight on their descriptional power.
Related content


Regular binoid expressions and regular binoid languages
By Hashiguchi K. Wada Y. Jimbo S.
Theoretical Computer Science, Vol. 304, Iss. 1, 2003-07 ,pp. :






Regular component decomposition of regular languages
By Liu Y.J.
Theoretical Computer Science, Vol. 299, Iss. 1, 2003-04 ,pp. :


On the acceptance power of regular languages
By Borchert B.
Theoretical Computer Science, Vol. 148, Iss. 2, 1995-09 ,pp. :