P. Bonizzoni, C. Ferretti, G. Mauri, R. Zizza
Separating some splicing models.
Abstract
In this paper we show that the three main definitions of the
splicing operation known in the literature, i.e. Head,
Paun and Pixton 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
how they cannot be generated by the smaller families.