Untersuchungen zu Kantengrammatiken und Valenzgrammatiken

Abstract

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.

The generation of graph families by edge grammars is investigated in this thesis. Edge grammars, introduced by F. Berman, generate binary word relations; a pair of words of length n is interpreted as an edge of the n-th graph. We investigate the generative power, closure and decidability properties of edge grammars. Important results are the decidability of the existence of graphs with properties definable by means of first order logic, the undecidability of the analogous problem for more complicated properties (e.g., connectedness), and the equivalence of a subfamily of edge grammars with parallel deterministic node replacement grammars. Valence grammars, as introduced by Paun, are grammars whose rules are valuated by elements of a given monoid. Only derivations with neutral valuations are allowed. In this thesis it is shown that formal languages generated by edge grammars can be characterized by valence grammars over the group (Z,+,0). The most important result on valence grammars is the construction of normal forms for valence grammars over the groups of k-dimensional integer vectors. Moreover, we investigate valence grammars generating slender languages. The results are finally used to show decidability of the membership problem for context-free edge grammars.