On bonded indian and uniformly parallel insertion systems and their generative power
DOI:
https://doi.org/10.11113/mjfas.v13n4.753Keywords:
Bonded parallel insertion systems, bonded Indian parallel insertion systems, bonded uniformly parallel insertion systems, formal languages, generative powerAbstract
Insertion is an operation in formal language theory that generalizes the operation of concatenation of words, where its variants allow the operation in different ways. Parallel insertion is a variant of insertion that simultaneously adds words between all letters of a word and also at the right and left extremities. In previous research, restrictions on the applicability have been imposed leading to so-called bonded insertion systems with a sequential and a parallel variant. Motivated by the atomic behavior of chemical compounds in the process of chemical bonding, the generative power of bonded insertion systems has been investigated where a language hierarchy was obtained. In this paper, we introduce new variants of bonded parallel insertion systems, namely bonded Indian parallel insertion systems and bonded uniformly parallel insertion systems. We present some results regarding the generative power of these new systems and a language hierarchy.References
Kari, L. 1991. On insertion and deletion in formal languages. Ph.D. thesis. University of Turku.
Cui, B., Kari, L., Seki, S. 2011. Block insertion and deletion on trajectories. Theoretical Computer Science. 412, 714-728.
Daley, M., Kari, L., Gloor, G., and Siromoney. R. Circular contextual insertions/deletions with applications to biomolecular computation. SPIRE/CRIWG. 47-54.
Ito, M., Kari, L., and Thierrin, G. 1997. Insertion and deletion closure of languages. Theoretical Computer Science. 183. 3-19.
Ito, M., Kari, L., and Thierrin, G. 2000. Shuffle and scattered deletion closure of languages. Theoretical Computer Science. 245(1), 115-133.
Kari, L. 1992. Insertion and deletion of words: determinism and reversibility. Mathematical Foundations of Computer Science. 315-327.
Kari, L. 1993. Generalized derivatives. Fundamenta Informaticae. 18(1), 61-77.
Kari, L., Mateecu, A., Paun, G., and Salomaa, A. 1993. Deletion sets. Fundamenta Informaticae. 19, 355-370.
Kari, L., Mateecu, A., Paun, G., and Salomaa, A. 1995. On parallel deletions applied to a word. RAIRO – Theoretical Informatics and Applications. 29(2), 129-144.
Kari, L., Paun, G., Thierrin, G., and Yu, S. 1999, ‘At the crossroads of DNA computing and formal languages: characterizing RE using insertion-deletion systems’ in Proceedings of 3rd DIMACS Workshop on DNA Based Computing, University of Pennsylvania, Pennsylvania, pp. 329-347.
Kari, L., and Thierrin, G. 1996. Contextual insertions/deletions and computability. Information and Computation. 131(1), 47-61.
Krassovitskiy, A. 2011. Complexity and modeling power of insertion-deletion systems. Ph.D. thesis. Universitat Rovira i Virgili.
Fong W. H., Holzer, M., Truthe, B., Turaev, S., and Yosman, A. F. 2016, ‘On bonded sequential and parallel insertion systems’ in Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA), ed. Bordihn, H. et al, Debrecen, Austria, pp. 163-178.
Rozenberg, G., and Salomaa, A. (1980). The Mathematical Theory of L-systems. Cambridge, MA: Academic Press.
Rozenberg, G., and Salomaa, A. (1997). Handbook of Formal Languages. Berlin: Springer-Verlag.
