In der vorliegenden Arbeit wird die Erzeugung von Graphenfamilien durch Kantengrammatiken untersucht. Die von F. Berman eingeführten Kantengrammatiken erzeugen binäre Wortrelationen; ein Paar von Wörtern der Länge n wird als Kante im n-ten Graphen interpretiert. In dieser Dissertation werden die Erzeugungsmächtigkeit, Abschluß- und Entscheidbarkeitseigenschaften von Kantengrammatiken untersucht. Wichtige Resultate sind die Entscheidbarkeit der Existenz von Graphen mit Eigenschaften, die durch Logik 1. Stufe beschreibbar sind, und die Unentscheidbarkeit des analogen Problems für kompliziertere Eigenschaften, sowie die Äquivalenz einer Teilklasse zu parallelen deterministischen Knotenersetzungs-Grammatiken. Die von Paun eingeführten Valenzgrammatiken sind Grammatiken, deren Regeln durch Elemente aus einem gegebenen Monoid bewertet sind. Zulässig sind mit dem neutralen Element bewertete Ableitungen. In der Arbeit wird gezeigt, daß sich die von Kantengrammatiken erzeugten formalen Sprachen durch Valenzgrammatiken über der Gruppe (Z,+,0) charakterisieren lassen. Das wichtigste Resultat zu Valenzgrammatiken ist die Konstruktion von Normalformen für Valenzgrammatiken über den Gruppen der k-dimensionalen ganzzahligen Vektoren. Außerdem werden Valenzgrammatiken, die schlanke Sprachen erzeugen, näher untersucht. Ergebnisse werden schließlich benutzt, um die Entscheidbarkeit des Elementproblems für kontextfreie Kantengrammatiken zu zeigen.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||