Title of Master's thesis: Teams in grammar systems

Abstract

This master's thesis consists of four parts. Part I is an introduction into the field of research of this thesis. The history and motivation of the theory of grammar systems is presented and an informal introduction of the notion of teams is given. 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, still producing one language.

After the introduction, Part II contains the prerequisites necessary for understanding this thesis. These are organized in such a way as to allow the reader to skip sections which would not extend his knowledge. The formal definitions of grammar systems can be found here as well.

In Part III, the forming of teams in grammar systems is studied. A team is formed from 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. Several derivation modes are considered, varying from using a team exactly one time to using it a maximal amount of times. The possibility of different teams having different modes of derivation is defined as well, as is a weaker restriction on the application of a team. The power of all such mechanisms is investigated exhaustively and in many cases the forming of teams enlarges the generative power of the underlying grammar systems. Finally, some variations with mechanisms controlling the derivations are defined and also their generative power is investigated.

In Part IV, finally, an enhanced grammar system, called an eco-grammar system, is studied. These systems were introduced by motivations coming from Artificial Life and (thus) consist of an environment in the form of a Lindenmayer system and agents working on this environment by context-free productions. Their application in Artificial Life is shortly discussed, but attention is focused on their language generative capacity. Several different ways of forming teams of agents, with different L systems for the environment, are introduced to mirror the investigations in Part III. Also in this case the forming of teams is found to increase the generative power of the underlying systems.


This research was supported by a scholarship from the Hungarian Ministry of Culture and Education. Moreover, the facilities provided by the Department of General Computer Science of the Eötvös Loránd University and in particular by the Computer and Automation Research Institute of the Hungarian Academy of Sciences were essential.