Geodesic
Extending regular expressions with homomorphic replacement
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 2, pp. 229-255

Voir la notice de l'article provenant de la source Numdam

We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem.

DOI : 10.1051/ita/2010013
Classification : 03D40, 68Q42, 68Q45
Keywords: regular languages, homomorphic replacement, computational complexity 
@article{ITA_2010__44_2_229_0,
     author = {Bordihn, Henning and Dassow, J\"urgen and Holzer, Markus},
     title = {Extending regular expressions with homomorphic replacement},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {229--255},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {2},
     year = {2010},
     doi = {10.1051/ita/2010013},
     mrnumber = {2674542},
     zbl = {1208.68134},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2010013/}
}
TY  - JOUR
AU  - Bordihn, Henning
AU  - Dassow, Jürgen
AU  - Holzer, Markus
TI  - Extending regular expressions with homomorphic replacement
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 229
EP  - 255
VL  - 44
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2010013/
DO  - 10.1051/ita/2010013
LA  - en
ID  - ITA_2010__44_2_229_0
ER  - 
%0 Journal Article
%A Bordihn, Henning
%A Dassow, Jürgen
%A Holzer, Markus
%T Extending regular expressions with homomorphic replacement
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 229-255
%V 44
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2010013/
%R 10.1051/ita/2010013
%G en
%F ITA_2010__44_2_229_0
Bordihn, Henning; Dassow, Jürgen; Holzer, Markus. Extending regular expressions with homomorphic replacement. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 2, pp. 229-255. doi: 10.1051/ita/2010013

Cité par Sources :