Title of talk: Teams in grammar systems


In contrast to classical formal language theory, which considers one grammar producing one language, a grammar system is a set of grammars, cooperating in a specified way, but still producing one language. A team consists of a finite number of components (sets of productions) and in every derivation step, one production from each component is used to rewrite a symbol of the sentential form. Hence rewriting is done in parallel.

The power of such mechanisms, including many variants, is studied in the first part of my master's thesis. An overview of the results was presented here in Leiden last December. This presentation will deal with the second part of my thesis: teams in simple eco-grammar systems.

The introduction of eco-grammar systems was motivated by considerations concerning Artificial Life and they (thus) consist of an environment in the form of a Lindenmayer system and agents working on this environment by context-free productions. Several different ways of forming teams of agents, with different L systems for the environment, are introduced. Furthermore, two different rewriting steps are introduced.

The forming of teams is found to increase the generative power of the underlying systems. Moreover, by proving some closure properties, one of the rewriting steps is shown to lead to a new characterization of the class of recursively enumerable languages.