In this paper we show that the three main definitions of the splicing operation known in the literature, i.e., the Head [Bull. Math. Biology 49 (1987) 737-759], Paun [Theoret. Comput. Sci. 168 (1996) 321-326] and Pixton [Discrete Appl. Math. 69 (1996) 101-124] definitions, give rise to different subclasses of regular languages, when a finite set of rules is iterated on a finite set of axioms. More precisely, we show that the family of regular languages generated by finite splicing, as defined in the early paper by Head, is strictly included in the family defined later by Paun, which is in turn strictly included in the splicing family defined by Pixton. We describe instance languages in the difference sets, and we prove that they cannot be generated by the smaller families.
Bonizzoni, P., Ferretti, C., Mauri, G., Zizza, R. (2001). Separating some splicing models. INFORMATION PROCESSING LETTERS, 79(6), 255-259 [10.1016/S0020-0190(01)00139-9].
Separating some splicing models
BONIZZONI, PAOLA;FERRETTI, CLAUDIO;MAURI, GIANCARLO;
2001
Abstract
In this paper we show that the three main definitions of the splicing operation known in the literature, i.e., the Head [Bull. Math. Biology 49 (1987) 737-759], Paun [Theoret. Comput. Sci. 168 (1996) 321-326] and Pixton [Discrete Appl. Math. 69 (1996) 101-124] definitions, give rise to different subclasses of regular languages, when a finite set of rules is iterated on a finite set of axioms. More precisely, we show that the family of regular languages generated by finite splicing, as defined in the early paper by Head, is strictly included in the family defined later by Paun, which is in turn strictly included in the splicing family defined by Pixton. We describe instance languages in the difference sets, and we prove that they cannot be generated by the smaller families.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
