J. Hromkovic et al., SOME HIERARCHIES FOR THE COMMUNICATION COMPLEXITY-MEASURES OF COOPERATING GRAMMAR SYSTEMS, Theoretical computer science, 127(1), 1994, pp. 123-147
Citations number
15
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
We investigate here the descriptional and the computational complexity
of parallel communicating grammar systems (PCGS), A new descriptional
complexity measure - the communication structure of the PCGS is intro
duced and related to the communication complexity (the number of commu
nications). Several hierarchies resulting from these complexity measur
es and some relations between the measures are established. The result
s are obtained due to the development of two lower-bound proof techniq
ues for PCGS. The first one is a generalization of pumping lemmas from
formal language theory and the second one reduces the lower-bound pro
blem for some PCGS to the proof of lower bounds on the number of rever
sals of certain sequential computing models.