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.

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
Mots-clés : 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://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] B. Cui, L. Kari and S. Seki, Block insertion and deletion on trajectories. Theoret. Comput. Sci. 412 (2011) 714–728 | DOI | MR | Zbl

[2] M. Daley, L. Kari, G. Gloor and R. Siromoney, 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] D. Haussler, Insertion languages. Inform. Sci. 31 (1983) 77–89 | DOI | MR | Zbl

[4] W. Heng Fong, M. Holzer, B. Truthe, S. Turaev and A. Firdaus Yosman 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 H. Bordihn, R. Freund, B. Nagy and G. Vaszil. Vol. 321 of books@ocg.at. Österreichische Computer Gesellschaft Austria (2016) 163–178

[5] G.T. Hermann and G. Rozenberg. Developmental Systems and Languages. North-Holland/American Elsevier, 1975 | MR | Zbl

[6] M. Ito, L. Kari and G. Thierrin, Insertion and deletion closure of languages. Theoret. Comput. Sci. 183 (1997) 3–19 | DOI | MR | Zbl

[7] M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theoret. Comput. Sci. 245 (2000) 115–133 | DOI | MR | Zbl

[8] L. Kari, On insertion and deletion in formal languages. Ph. D. thesis, University of Turku (1991) | MR

[9] L. Kari, 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] L. Kari, Generalized derivatives. Fund. Inform. 18 (1993) 61–77 | MR | Zbl

[11] L. Kari, Insertion operation: closure properties. Eur. Assoc. Theoret. Comput. Sci. Bull. 51 (1993) 181–191 | Zbl

[12] L. Kari, Deletion operations: closure properties. Int. J. Comput. Math. 52 (1994) 23–42 | DOI

[13] L. Kari, 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] L. Kari, A. Mateescu, G. Păun and A. Salomaa, Deletion sets. Fund. Inform. 19 (1993) 355–370 | MR | Zbl

[15] L. Kari, A. Mateescu, G. Păun and A. Salomaa, On parallel deletions applied to a word. RAIRO: ITA 29 (1995) 129–144 | Numdam | MR | Zbl

[16] L. Kari, G. Păun, G. Thierrin and S. Yu, 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] L. Kari and S. Seki, Schema for parallel insertion and deletion: revisited. Int. J. Found. Comput. Sci. 22 (2011) 1655–1668 | DOI | MR | Zbl

[18] L. Kari and P. Sosík, Aspects of shuffle and deletion on trajectories. Theoret. Comput. Sci. 332 (2005) 47–61 | DOI | MR | Zbl

[19] L. Kari and G. Thierrin, Contextual insertions/deletions and computability. Inform. Comput. 131 (1996) 47–61 | DOI | MR | Zbl

[20] A. Krassovitskiy, Complexity and modeling power of insertion-deletion systems. Ph. D. thesis, Universitat Rovira i Virgili (2011)

[21] G. Păun, G. Rozenberg and A. Salomaa, DNA Computing: New Computing Paradigms. Springer-Verlag (1998) | DOI | MR | Zbl

[22] J.B. Reece, L.A. Urry, M.L. Cain, S.A. Wasserman, P.V. Minorsky and R.B. Jackson,

[23] G. Rozenberg and A. Salomaa, The Mathematical Theory of L-systems. Academic Press (1980) | MR | Zbl

[24] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin (1997) | MR | Zbl

[25] A. Firdaus Yosman, M. Holzer, B. Truthe, W. Heng Fong and S. Turaev, 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 :