| Issue |
RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|
|
|---|---|---|
| Page(s) | 127 - 151 | |
| DOI | https://doi.org/10.1051/ita/2018010 | |
| Published online | 15 January 2019 | |
Regular Article
On bonded sequential and parallel insertion systems★
1
Institut für Informatik, Universität Giessen,
Arndtstr. 2,
35392 Giessen, Germany.
2
Department of Mathematical Sciences, Faculty of Science, Universiti Teknologi Malaysia,
81310 UTM Johor Bahru,
Johor, Malaysia.
* Corresponding author: holzer@informatik.uni-giessen.de
Accepted: 21 November 2018
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.
Mathematics Subject Classification: 68Q42 / 68Q45
Key words: Bonded insertion systems / sequential insertion / parallel insertion / formal languages / generative power
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.