On graph rewritings. (English) Zbl 0551.68065

This paper deals with rewriting of directed ordered graphs over a graded alphabet G. The author shows that if graphs are represented by vertices and edges direct derivations accordin to H. Ehrig, M. Pfender, and H. J. Schneider [Graph Grammars: an algebraic approach, Proc. 14th Annual Conf. Switching Automata Theory, 167-180 (1973)] can be simulated using a single push-out of partial morphisms. In the following graphs representing terms of the free G-algebra over a given set of variables are considered. Let A, B, C be graphs, \(f: A\to B\) a total function and \(g: A\to C\) be an occurrence, then the push-out of f and g yields a unique graph structure D provided that certain conditions are satisfied. If A, B, C represent terms exp(A), exp(B), exp(C) and f is associated with a term rewriting rule exp(A)\(\to \exp (B)\), then D represents a term exp(D) which one obtains by applying the rule exp(A)\(\to \exp (B)\) to exp(C). Finally the author gives a necessary and sufficient condition for local confluence of a final system of graph rewriting rules associated with term rewriting rules. In the framework of graph grammars according to the Berlin School a similar result holds using the embedding theorem [cf. H. Ehrig, Lect. Notes Comput. Sci. 73, 1-69 (1979; Zbl 0407.68072)].
Reviewer: U.Hummert


68Q45 Formal languages and automata
68Q65 Abstract data types; algebraic specification


Zbl 0407.68072
Full Text: DOI


[1] Barendregt, H. P., The Lambda Calculus, Its Syntax and Semantics, (Studies in Logic and the Foundations of Mathematics, 103 (1981), North-Holland: North-Holland Amsterdam) · Zbl 0467.03010
[2] Cocke, J.; Schwartz, J. T., Programming Languages and Their Compilers (1970), Courant Institute of Mathematical Science: Courant Institute of Mathematical Science New York, (Preliminary notes) · Zbl 0245.68003
[3] Ehrig, H.; Pfender, M.; Schneider, H. J., Graph grammars: An algebraic approach, Proc. 14th Ann. IEEE Symp. on Switching and Automata Theory, 167-180 (1973), Iowa City
[4] Huet, G., Confluent reductions, abstract properties and application to term rewriting systems, J. ACM, 27, 4, 797-821 (1980) · Zbl 0458.68007
[5] Knuth, D. E.; Bendix, P.; Leech, J., Simple word problems in universal algebras, Computational Problems in Abstract Algebras (1970), Pergamon Press: Pergamon Press Braunschweig · Zbl 0188.04902
[6] Lévy, J.-J., Réductions correctes et optimales dans le lambda-calcul, (Thèse d’état (1978), Univ. Paris VII)
[7] Montangero, C.; Picini, G.; Turini, F., Graph representation and computation rules for typeless recursive program schemes, 2nd Colloq. on Automata, Languages and Programming, 14 (1974), Springer: Springer Berlin, Saarbrücken, Lecture Notes in Comput. Sci. · Zbl 0297.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.