Voir la notice de l'article provenant de la source Numdam
A permutation rule is a non-context-free rule whose both sides contain the same multiset of symbols with at least one non-terminal. This rule does not add or substitute any symbols in the sentential form, but can be used to change the order of neighbouring symbols. In this paper, we consider regular and linear grammars extended with permutation rules. It is established that the generative power of these grammars relies not only on the length of the permutation rules, but also whether we allow or forbid the usage of erasing rules. This is quite surprising, since there is only one non-terminal in sentential forms of derivations for regular or linear grammars. Some decidability problems and closure properties of the generated families of languages are investigated. We also show a link to a similar model which mixes the symbols: grammars with jumping derivation mode.
Madejski, Grzegorz 1
@article{ITA_2018__52_2-3-4_219_0,
author = {Madejski, Grzegorz},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {Regular and linear permutation languages},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {219--234},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018016},
mrnumber = {3915310},
zbl = {1429.68125},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018016/}
}
TY - JOUR AU - Madejski, Grzegorz ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Regular and linear permutation languages JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 219 EP - 234 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018016/ DO - 10.1051/ita/2018016 LA - en ID - ITA_2018__52_2-3-4_219_0 ER -
%0 Journal Article %A Madejski, Grzegorz %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Regular and linear permutation languages %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 219-234 %V 52 %N 2-3-4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018016/ %R 10.1051/ita/2018016 %G en %F ITA_2018__52_2-3-4_219_0
Madejski, Grzegorz. Regular and linear permutation languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 219-234. doi: 10.1051/ita/2018016
Cité par Sources :