Home
Scholarly Works
Collapsing hierarchies in PCGSs with communication...
Journal article

Collapsing hierarchies in PCGSs with communication by command

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.

Authors

Ilie L

Journal

Computers and Artificial Intelligence, Vol. 15, No. 2-3, pp. 173–184

Publication Date

January 1, 1996

ISSN

0232-0274

Contact the Experts team