Kybernetika 31 no. 1, 83-97, 1995

On the generative capacity of colonies

Gheorghe Păun


We consider here colonies (grammar systems having as components regular grammars generating finite languages) with various derivation modes ($*, t, \le k, = k, \ge k$, as usual in grammar systems area). Their generative capacity is investigated. Problems still open in the theory of general grammar systems (concerning, for instance, hierarchies on the number of components and on the parameter $k$ mentioned above) are solved for this particular case. When hypothesis languages are added or the cooperation is aided by a transducer, the family of context-sensitive languages is characterized in most of these derivation modes.


68Q42, 68Q45, 68Q50