Prescribed teams of grammars (Q1338898)

A cooperating grammar system consists of several context-free grammars working together, by turns, on a common sentential form. In each moment, one component is active, the others are inactive. Details can be found in the monograph Grammar Systems, by \textit{E. Csuhaj-Varju}, \textit{J. Dassow}, \textit{J. Kelemen} and \textit{Gh. Păun} (1994). Recently, \textit{L. Kari}, \textit{Al Mateescu}, \textit{Gh. Păun} and \textit{A. Salomaa} [Teams in cooperating grammar systems, J. Experimental Applied Al (1994)] have considered systems where more components work simultaneously (this is a team, nondeterministically formed, but with a given size). The present paper investigates grammar systems with prescribed teams. In the case of the maximal derivation mode (a team works as long as it can, in two variants, depending on whether or not part of the team members can still work), characterizations of languages generated by programmed grammars with appearance checking are obtained, namely by grammar systems with teams of size two. Some problems left open in the mentioned paper by L. Kari et al. are solved in this way. For other modes of derivation (a team works \(k\) steps, at most \(k\) or at least \(k\) steps), characterizations of programmed languages generated without appearance checking are obtained.