Conference paper

Publication year: 2018

Pages: 127-151

Journal: RAIRO: Theoretical Informatics and Applications

Volume number: 52

Issue number: 2-4

ISSN: 0988-3754

eISSN: 1290-385X

Open access status: Green

DOI Link: https://doi.org/10.1051/ita/2018010

Conference: 8th Workshop on Non-Classical Models of Automata and Applications (NCMA)

Publisher: EDP Sciences

Abstract: 
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.

Harvard Citation style: Holzer, M., Truthe, B. and Yosman, A. (2018) ON BONDED SEQUENTIAL AND PARALLEL INSERTION SYSTEMS, RAIRO: Theoretical Informatics and Applications, 52(2-4), pp. 127-151. https://doi.org/10.1051/ita/2018010

APA Citation style: Holzer, M., Truthe, B., & Yosman, A. (2018). ON BONDED SEQUENTIAL AND PARALLEL INSERTION SYSTEMS. RAIRO: Theoretical Informatics and Applications. 52(2-4), 127-151. https://doi.org/10.1051/ita/2018010