Apex graph grammars and attribute grammars (Q1112623)

In diesem Artikel werden die ADG Graph-Grammatiken (attribute dependency graph grammars) definiert und mit anderen Klassen von Graph-Grammatiken verglichen. Die Untersuchung ist anhand der DNLC (directed node-label controlled) Graph-Grammatiken durchgeführt, die auf dem Rewriting- Mechanismus von kontextfreien Sprachen basieren. Es wird gezeigt, daß die ADG Klasse in der Klasse der A1-DNCE (apex 1DNCE) Graph-Grammatiken enthalten ist, aber nicht in A-DNLC (apex DNLC). Die ADG Klasse ist in der Klasse R(A-DNLC) (wobei R für Umbenennung steht) enthalten. Die Klasse R(A-DNLC) ist die kleinste Klasse von Graph-Sprachen, die ADG enthält und bezüglich der ``Replacements'' (Nodesubstitution durch einen ``kleinen'' Graphen) abgeschlossen ist. Die Arbeit ist die Fortsetzung der Arbeiten von Rozenberg, Leih, Ehrig, Kreowski, Rosenfeld in der Theorie der Graph-Grammatiken.