SOME HIERARCHIES FOR THE COMMUNICATION COMPLEXITY-MEASURES OF COOPERATING GRAMMAR SYSTEMS

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.