ON THE POWER OF PARALLEL COMMUNICATING GRAMMAR SYSTEMS WITH RIGHT-LINEAR COMPONENTS

Authors
DUMITRESCU S PAUN G
Citation
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
Citations number
12
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
31
Issue
4
Year of publication
1997
Pages
331 - 354
Database
ISI
SICI code
0988-3754(1997)31:4<331:OTPOPC>2.0.ZU;2-O
Abstract
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.