Collapsing Hierarchies in PCGSs with Communication by Commands

Abstract

We investigate here, mainly from the point of view of the hierarchies generated by different classes of systems, two variants of the parallel communicating grammar systems (PCGS) with communication by command:  the multiple and, respectively, the single communication case. We show that the hierarchies for regular and linear components collapse in the single communication case and the hierarchy for context-sensitive components collapses in both multiple and single communication cases. By a result in [3], it will follow from our result on systems with context-sensitive components that also the hierarchy for context-free components collapses in both cases. Some open problems are also formulated.