Collapsing Hierarchies in PCGSs with Communication by Commands


  • L. Ilie


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.


Download data is not yet available.



How to Cite

Ilie, L. (2012). Collapsing Hierarchies in PCGSs with Communication by Commands. COMPUTING AND INFORMATICS, 15(2-3), 173–184. Retrieved from