×

On bonded sequential and parallel insertion systems. (English) Zbl 1429.68116

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

MSC:

68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Cui, L. Kari and S. Seki, Block insertion and deletion on trajectories. Theoret. Comput. Sci.412 (2011) 714-728 · Zbl 1206.68170 · doi:10.1016/j.tcs.2010.11.009
[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 · Zbl 0544.68049 · doi:10.1016/0020-0255(83)90023-3
[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 · Zbl 0306.68045
[6] M. Ito, L. Kari and G. Thierrin, Insertion and deletion closure of languages. Theoret. Comput. Sci. 183 (1997) 3-19 · Zbl 0901.68097 · doi:10.1016/S0304-3975(96)00307-6
[7] M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theoret. Comput. Sci. 245 (2000) 115-133 · Zbl 0946.68074 · doi:10.1016/S0304-3975(99)00277-7
[8] L. Kari, On insertion and deletion in formal languages. Ph. D. thesis, University of Turku (1991)
[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 · Zbl 1493.68283
[10] L. Kari, Generalized derivatives. Fund. Inform. 18 (1993) 61-77
[11] L. Kari, Insertion operation: closure properties. Eur. Assoc. Theoret. Comput. Sci. Bull. 51 (1993) 181-191 · Zbl 0787.68061
[12] L. Kari, Deletion operations: closure properties. Int. J. Comput. Math. 52 (1994) 23-42
[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 · Zbl 07795996 · doi:10.1007/3-540-58131-6_48
[14] L. Kari, A. Mateescu, G. Păun and A. Salomaa, Deletion sets. Fund. Inform. 19 (1993) 355-370 · Zbl 0787.68062
[15] L. Kari, A. Mateescu, G. Păun and A. Salomaa, On parallel deletions applied to a word. RAIRO: ITA29 (1995) 129-144 · Zbl 0816.68095
[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 · Zbl 0946.68084
[17] L. Kari and S. Seki, Schema for parallel insertion and deletion: revisited. Int. J. Found. Comput. Sci. 22 (2011) 1655-1668 · Zbl 1252.68176 · doi:10.1142/S0129054111008945
[18] L. Kari and P. Sosík, Aspects of shuffle and deletion on trajectories. Theoret. Comput. Sci. 332 (2005) 47-61 · Zbl 1070.68071 · doi:10.1016/j.tcs.2004.09.038
[19] L. Kari and G. Thierrin, Contextual insertions/deletions and computability. Inform. Comput. 131 (1996) 47-61 · Zbl 0872.68038 · doi:10.1006/inco.1996.0091
[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) · Zbl 0940.68053
[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) · Zbl 0508.68031
[24] G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin (1997) · Zbl 0866.68057
[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:10.11113/mjfas.v13n4.753
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.