Geodesic
Expressive capacity of subregular expressions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 201-218

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

Different types of subregular expressions are studied. Each type is obtained by either omitting one of the regular operations or replacing it by complementation or intersection. For uniformity and in order to allow non-trivial languages to be expressed, the set of literals is a finite set of words instead of letters. The power and limitations as well as relations with each other are considered, which is often done in terms of unary languages. Characterizations of some of the language families are obtained. A finite hierarchy is shown that reveals that the operation complementation is generally stronger than intersection. Furthermore, we investigate the closures of language families described by regular expressions with omitted operation under that operation. While it is known that in case of union this closure captures all regular languages, for the cases of concatenation and star incomparability results are obtained with the corresponding language families where the operation is replaced by complementation.

Reçu le :
DOI : 10.1051/ita/2018014
Classification : 68Q45, 68Q15
Keywords: Regular expressions, concatenation-free languages, star-free languages, union-free languages, expressive capacity, characterizations, closure properties, subregular hierarchy

Kutrib, Martin 1 ; Wendlandt, Matthias 1

1 
@article{ITA_2018__52_2-3-4_201_0,
     author = {Kutrib, Martin and Wendlandt, Matthias},
     editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
     title = {Expressive capacity of subregular expressions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {201--218},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2-3-4},
     year = {2018},
     doi = {10.1051/ita/2018014},
     mrnumber = {3915309},
     zbl = {1475.68162},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018014/}
}
TY  - JOUR
AU  - Kutrib, Martin
AU  - Wendlandt, Matthias
ED  - Bordihn, Henning
ED  - Nagy, Benedek
ED  - Vaszil, György
TI  - Expressive capacity of subregular expressions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 201
EP  - 218
VL  - 52
IS  - 2-3-4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018014/
DO  - 10.1051/ita/2018014
LA  - en
ID  - ITA_2018__52_2-3-4_201_0
ER  - 
%0 Journal Article
%A Kutrib, Martin
%A Wendlandt, Matthias
%E Bordihn, Henning
%E Nagy, Benedek
%E Vaszil, György
%T Expressive capacity of subregular expressions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 201-218
%V 52
%N 2-3-4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018014/
%R 10.1051/ita/2018014
%G en
%F ITA_2018__52_2-3-4_201_0
Kutrib, Martin; Wendlandt, Matthias. Expressive capacity of subregular expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 201-218. doi: 10.1051/ita/2018014

Cité par Sources :