On graph rewritings. (English) Zbl 0551.68065

Raoult, Jean Claude

Theor. Comput. Sci. 32, 1-24 (1984).

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

MSC:

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

Keywords:

local confluence; graph rewriting; term rewriting; graph grammars

Citations:

Zbl 0407.68072

References:

[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