On the closure of pattern expressions languages under intersection with regular languages

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.

Previous Menu Next

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.