Weighted Simple and Semi-Simple Splicing Systems
DOI:
https://doi.org/10.11113/mjfas.v10n4.324Keywords:
weights, simple, semi-simple, splicing system, generative power, Chomsky hierarchyAbstract
The modelling of splicing system has been introduced theoretically by Head in 1987. As time goes on, various splicing systems have been developed, such as one-sided, simple and semi-simple splicing systems. However, in the investigation on the generative power of splicing system, there are limitations on the generative power of splicing system with finite components. In order to overcome the limitation of the usual splicing system, one variant of splicing system has been introduced recently, called the weighted splicing system. In this paper, we associate weights from selected weighting spaces to the axioms of simple and semi-simple splicing systems, thus introducing weighted simple splicing system and weighted semi-simple splicing system. Some examples are presented for weighted simple and semi-simple splicing systems to illustrate their generative power. Lastly, relation of the languages generated by weighted simple and semi-simple splicing systems in the Chomsky hierarchy are also investigated.
References
T. Head. Bull. Math. Biol,, 49(6) (1987) 737 – 759.
G. Paun, G. Rozenberg. A. Salomaa. DNA Computing: New Computing Paradigms. Berlin, Springer-Verlag, 1998, 217 – 305.
D. Pixton. Discrete Appl. Math., 69 (1996) 101 – 124.
R. Freund, L. Kari, Gh. Paun. Theory Comput. Syst., 32 (1999) 69 – 112.
Gh. Paun, J. Autom. Lang. Comb., 1(1) (1996) 27–37,
S. Turaev, Y.S. Gan, M. Othman, N.H. Sarmin and W.H. Fong. In Computational Intelligence and Intelligent Systems. (eds. Z. Li, X. Li, Y. Liu, Z. Cai), China, Springer, 2012, 416 – 424.
A. Salomaa. Inform Control., 15 (1969) 529 – 544.
K.S. Fu, T. Li. Inform. Sci., 1(4) (1969) 403 – 419.
M. Mizumoto, J. Toyoda, K. Tanaka. Inform. Process. Lett., 2(3) (1973) 74 – 78.
M. Mizumoto, J. Toyoda, K. Tanaka. J. Comput. Syst. Sci. Int., 10(2) (1975) 219 – 236.
A. Alexandrakis, S. Bozapalidis. Inform. Process. Lett. 24(1) (1987) 1 – 4.
M. Droste, W. Kuich, H. Vogler. Handbook of Weighted Automata. Berlin, Springer-Verlag, 2009, 69 – 208.
G. Rozenberg, A. Salomaa, Handbook of Formal Languages. Berlin, Springer-Verlag, 1997, 1 – 150.
J. Dassow, G. Paun. Regulated Rewriting in Formal Language Theory. Berlin, Springer-Verlag, 1989, 9 – 18.
P. Linz. An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers. 2006.
A. Mateescu, Gh. Paun, G. Rozenberg, A. Salomaa. Simple Splicing Systems. Discrete Appl. Math. 84 (1998) 145 – 163.
E. Goode, D. Pixton, Semi-simple splicing systems, in: Where Mathematics, Computer Science, Linguistics and Biology Meet. (eds. C. Martine-Vide, V. Mitrana), Dordrecht, Kluwer Academic Publ, 2001, 343 – 357.
