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.
DOI : 10.1051/ita/2018010
Mots clés : Bonded insertion systems, sequential insertion, parallel insertion, formal languages, generative power
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2018010/
[1] , and , Block insertion and deletion on trajectories. Theoret. Comput. Sci. 412 (2011) 714–728 | DOI | MR | Zbl
[2] , , and , Circular contextual insertions/deletions with applications to biomolecular computation, in SPIRE/CRIWG, Cancun, Mexico, September 21–24, 1999. IEEE Computer Society Press (1999) 47–54
[3] , Insertion languages. Inform. Sci. 31 (1983) 77–89 | DOI | MR | Zbl
[4] , , , and On bonded sequential and parallel insertion systems, in Proc. 8th Workshop on Non-Classical Models of Automata and Applications (NCMA), Debrecen, Hungary, August 29–30, 2016, edited by , , and . Vol. 321 of books@ocg.at. Österreichische Computer Gesellschaft Austria (2016) 163–178
[5] and Developmental Systems and Languages. North-Holland/American Elsevier, 1975 | MR | Zbl
[6] , and , Insertion and deletion closure of languages. Theoret. Comput. Sci. 183 (1997) 3–19 | DOI | MR | Zbl
[7] , and , Shuffle and scattered deletion closure of languages. Theoret. Comput. Sci. 245 (2000) 115–133 | DOI | MR | Zbl
[8] , On insertion and deletion in formal languages. Ph. D. thesis, University of Turku (1991) | MR
[9] , Insertion and deletion of words: determinism and reversibility, in Mathematical Foundations of Computer Science. Vol. 629 of Lect. Notes Comput. Sci. Springer (1992) 315–327 | DOI | MR
[10] , Generalized derivatives. Fund. Inform. 18 (1993) 61–77 | MR | Zbl
[11] , Insertion operation: closure properties. Eur. Assoc. Theoret. Comput. Sci. Bull. 51 (1993) 181–191 | Zbl
[12] , Deletion operations: closure properties. Int. J. Comput. Math. 52 (1994) 23–42 | DOI
[13] , Power of controlled insertion and deletion, in Proc. of Results and Trends in Theoretical Computer Science, Colloquium in Honor of Arto Salomaa, Graz, Austria, June 10–11, 1994. Vol. 812 of Lect. Notes Comput. Sci. Springer (1994) 197–212 | DOI | MR
[14] , , and , Deletion sets. Fund. Inform. 19 (1993) 355–370 | MR | Zbl
[15] , , and , On parallel deletions applied to a word. RAIRO: ITA 29 (1995) 129–144 | Numdam | MR | Zbl
[16] , , and , At the crossroads of dna computing and formal languages: characterizing re using insertion–deletion systems, in Proc. of 3rd DIMACS Workshop on DNA Based Computing (1997) 318–333
[17] and , Schema for parallel insertion and deletion: revisited. Int. J. Found. Comput. Sci. 22 (2011) 1655–1668 | DOI | MR | Zbl
[18] and , Aspects of shuffle and deletion on trajectories. Theoret. Comput. Sci. 332 (2005) 47–61 | DOI | MR | Zbl
[19] and , Contextual insertions/deletions and computability. Inform. Comput. 131 (1996) 47–61 | DOI | MR | Zbl
[20] , Complexity and modeling power of insertion-deletion systems. Ph. D. thesis, Universitat Rovira i Virgili (2011)
[21] , and , DNA Computing: New Computing Paradigms. Springer-Verlag (1998) | DOI | MR | Zbl
[22] , , , , and ,
[23] and , The Mathematical Theory of L-systems. Academic Press (1980) | MR | Zbl
[24] and , Handbook of Formal Languages. Springer-Verlag, Berlin (1997) | MR | Zbl
[25] , , , and , On bonded Indian and uniformly parallel insertion systems and their generative power. Mal. J. Fund. Appl. Sci. 13 (2017) 769–773 | DOI
Cité par Sources :
