Refine
Year of publication
- 2007 (1)
Document Type
- Doctoral Thesis (1) (remove)
Language
- German (1) (remove)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- Formale Grammatik (1) (remove)
Institute
- Informatik (1)
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.