Open Access

Bettina Sunckel

• In der klassischen Theorie der formalen Sprachen gehört die Beschreibung von Sprachen durch Grammatiken oder Automaten zu den wichtigen Themen. Im Gegensatz zu diesen Modellen, die aus einer einzelnen Komponente bestehen, beschäftigt sich die Informatik heute aber immer häufiger mit verteilten Systemen, deren Komponenten auf verschiedene Art und Weise zusammenarbeiten. Eine Möglichkeit, dieses Konzept auf die Theorie der formalen Sprachen zu übertragen, ist die Definition von Grammatiksystemen. Ein Grammatiksystem besteht aus mehreren Grammatiken, die nach bestimmten Regeln zusammenarbeiten. Hauptsächlich unterscheidet man dabei zwischen sequentieller und paralleler Kooperation. In dieser Arbeitwerden kontextfreie „cooperating distributed“ (CD) Grammatiksysteme, ein Modell mit sequentieller Kooperation, betrachtet. Zur Erzeugung eines Wortes arbeiten dabei mehrere kontextfreie Grammatiken, die Komponenten, an einer gemeinsamen Satzform. Zu jedem Zeitpunkt ist immer nur eine einzige Komponente aktiv. Der Schwerpunkt der Arbeit liegt auf der Beschreibungskomplexität von CD Grammatiksystemen. Dabei wird zuerst auf die verschiedenen Maße für die Größe oder statische Komplexität eines CD Grammatiksystems eingegangen. Ein wichtiges Ergebnis im ersten Teil der Arbeit ist, daß man für CD Grammatiksysteme und insbesondere hybride CD Grammatiksysteme, eine Verallgemeinerung von kontextfreien CD Grammatiksystemen, einige dieser Maße nach oben beschränken kann. Darunter fallen die Anzahl der Komponenten und die maximale Anzahl von Produktionen in einer Komponente. Hält man einen der beiden Parameter fest, so entsteht eine unendliche Hierarchie über dem anderen Parameter. Der zweite Teil der Arbeit konzentriert sich darauf, Ergebnisse für Größenmaße zu erzielen, die nicht nur einzelne Aspekte der Komplexität, sondern die gesamte Größe oder Länge eines CD Grammatiksystems darstellen. Dafür werden CD Grammatiksysteme geeignet eingeschränkt. Man erhält metalineare Systeme und Systeme von endlichem Index. Im Gegensatz zum unbeschränkten Modell kann hier die generative Mächtigkeit sehr genau charakterisiert werden und es können Hilfsmittel wie Pumpinglemmata gezeigt werden.Weitere Resultate sind eine unendliche Hierarchie über der Breite beziehungsweise dem Index solcher Grammatiksysteme. Das wesentliches Resultat im zweiten Teil dieser Arbeit besteht daraus, daß zwischen zwei Klassen von diesen eingeschränkten CD Grammatiksystemen, deren entsprechende Sprachklassen echt ineinander enthalten sind, nichtrekursive Tradeoffs existieren. Das heißt, daß sich der Größenzuwachs beim Wechsel von der stärkeren Klasse von CD Grammatiksystemen in die schwächere durch keine rekursive Funktion beschränken läßt.
• Grammar systems are models of distributed systems in terms of formal grammars. They consist of several components where each component is a grammar. Apart from a parallel model in which the components contribute to a derivation simultaneously, there are sequential models, namely the cooperating distributed (CD) grammar systems. At one point of time only one component contributes to the derivation and is called the active component. The derivation mode defines how long productions of a component can be used and when the next component becomes active. When investigating classes of grammars, not only the generative capacity but also the conciseness and the simplicity of the description of the generated language classes are of interest. In case we can describe a class of languages with two different types of language generating devices, the question arises, whether there are differences concerning the size of the description. First, we investigate descriptional complexity aspects of hybrid CD grammar systems. In contrast to the general CD grammar system the components of a hybrid CD grammar systeme each have a derivation mode of their own. For some hybrid CD grammar systems it is possible to find equivalent systems that consist of only five components. For these hybrid CD grammar systems we can also construct equivalent systems with at most six productions in a component. If one of the two parameters is fixed, the other one induces an infinite hierarchy of language classes. Metalinear CD grammar systems are context-free CD grammar systems where each component consists of metalinear productions. The maximal number of nonterminals in all starting productions is referred to as the width of a CD grammar system. We show that between the class of CD grammar systems of width m+1 and of width m there are savings concerning the size of the grammar system not bounded by any recursive function. This is called a non-recursive trade-off. Furthermore, it is proven that there are non-recursive trade-offs between the class of metalinear CD grammar systems of width m and the class of (2m-1)-linear context-free grammars. In addition, some decidability results are presented. When we restrict a context-free CD grammar system in such a way that for each word w in the generated language there has to be at least one derivation where only m or less nonterminals are present in each sentential form, we obtain the class of CD grammar systems of index m. It is proven that between the language class generated by CD grammar systems of index m+1 and of index m there are savings concerning the size of the description not bounded by any recursive function. Additionally, it is shown that there are non-recursive trade-offs between the class of languages generated by CD grammar systems of index m and metalinear CD grammar systems of width m.