Collapsing Hierarchies in PCGSs with Communication by Commands
L. Ilie
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
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.
Publié le : 2012-01-26
Classification: 
@article{cai699,
     author = {L. Ilie},
     title = {Collapsing Hierarchies in PCGSs with Communication by Commands},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai699}
}
L. Ilie. Collapsing Hierarchies in PCGSs with Communication by Commands. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai699/