S. Dumitrescu et G. Paun, ON THE POWER OF PARALLEL COMMUNICATING GRAMMAR SYSTEMS WITH RIGHT-LINEAR COMPONENTS, Informatique theorique et applications, 31(4), 1997, pp. 331-354
We settle here two problems concerning the generative power of paralle
l communicating grammar systems with right-linear components: (1) each
linear language can be generated by a non-centralized returning syste
m, (2) the family of languages generated by centralized returning syst
ems is incomparable with the family of languages generated by non-retu
rning centralized systems. It is also proved that centralized returnin
g systems with right-linear components are strictly more powerful than
systems with regular rules in the restricted sense.