Geodesic
On bonded sequential and parallel insertion systems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 127-151

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

We introduce a new variant of insertion systems, namely bonded insertion systems. In such systems, words are not only formed by usual letters but also by bonds between letters. Words which can be inserted, have “free” bonds at their ends which control at which positions in a word they can be inserted (namely only there, where the bonds “fit”). Two kinds of bonded insertion systems are defined in this paper: so-called bonded sequential insertion systems and bonded parallel insertion systems. In a sequential system, there is only one word inserted at a time. In a parallel system, there is a word inserted at every possible position in parallel in one time step. We investigate the generative capacity of those two kinds and relate the families of generated languages to some families of the Chomsky hierarchy and to families of languages generated by Lindenmayer systems. Additionally, we investigate some closure properties.

Accepté le :
DOI : 10.1051/ita/2018010
Classification : 68Q42, 68Q45
Keywords: Bonded insertion systems, sequential insertion, parallel insertion, formal languages, generative power

Holzer, Markus 1 ; Truthe, Bianca 1 ; Firdaus Yosman, Ahmad 1

1 
@article{ITA_2018__52_2-3-4_127_0,
     author = {Holzer, Markus and Truthe, Bianca and Firdaus Yosman, Ahmad},
     editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
     title = {On bonded sequential and parallel insertion systems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {127--151},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2-3-4},
     year = {2018},
     doi = {10.1051/ita/2018010},
     mrnumber = {3915305},
     zbl = {1429.68116},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018010/}
}
TY  - JOUR
AU  - Holzer, Markus
AU  - Truthe, Bianca
AU  - Firdaus Yosman, Ahmad
ED  - Bordihn, Henning
ED  - Nagy, Benedek
ED  - Vaszil, György
TI  - On bonded sequential and parallel insertion systems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 127
EP  - 151
VL  - 52
IS  - 2-3-4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018010/
DO  - 10.1051/ita/2018010
LA  - en
ID  - ITA_2018__52_2-3-4_127_0
ER  - 
%0 Journal Article
%A Holzer, Markus
%A Truthe, Bianca
%A Firdaus Yosman, Ahmad
%E Bordihn, Henning
%E Nagy, Benedek
%E Vaszil, György
%T On bonded sequential and parallel insertion systems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 127-151
%V 52
%N 2-3-4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018010/
%R 10.1051/ita/2018010
%G en
%F ITA_2018__52_2-3-4_127_0
Holzer, Markus; Truthe, Bianca; Firdaus Yosman, Ahmad. On bonded sequential and parallel insertion systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 127-151. doi: 10.1051/ita/2018010

Cité par Sources :