×
Bauderon, Michel; Courcelle, Bruno

Graph expressions and graph rewritings. (English) Zbl 0641.68115

Math. Syst. Theory 20, No. 2-3, 83-127 (1987).
Summary: We define an algebraic structure for the set of finite graphs, a notion of graph expression for defining them, and a complete set of equational rules for manipulating graph expressions. (By a graph we mean an oriented hypergraph, the hyperedges of which are labeled with symbols from a fixed finite ranked alphabet and that is equipped with a finite sequence of distinguished vertices.) The notion of a context-free graph grammar is introduced (based on the substitution of a graph for a hyperedge in a graph).
The notion of an equational set of graphs follows in a standard way from the algebraic structure. As in the case of context-free languages, a set of graphs is context-free iff it is equational. By working at the level of expressions, we derive from the algebraic formalism a notion of graph rewriting which is as powerful as the usual one (based on a categorical approach) introduced by Ehrig, Pfender, and Schneider.

Cited in 2 Reviews
Cited in 92 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

graph expressions; context-free graph grammar; equational set; graph rewriting

Software:

ALGOL 60
PDF BibTeX XML Cite
\textit{M. Bauderon} and \textit{B. Courcelle}, Math. Syst. Theory 20, No. 2--3, 83--127 (1987; Zbl 0641.68115)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Arnold, A., and Dauchet M., Théorie des magmoïdes,RAIRO Inform. Théor.,12 (1978), 235–257. · Zbl 0391.68037
[2] Bauderon M., On infinite graphs defined by equations, Research Report, Bordeaux I University (to appear). · Zbl 0762.05080
[3] Bloom, S., Elgot, C., and Wright J., Solutions to the iteration equation and extensions of the scalar iteration operation,SIAM J. Comput.,9 (1980), 25–45. · Zbl 0454.18011
[4] Courcelle, B., Fundamental properties of infinite trees,Theoret. Comput. Sci.,25 (1983), 95–169. · Zbl 0521.68013
[5] Courcelle, B., Equivalences and transformations of regular systems. Applications to recursive program schemes and grammars,Theoret. Comput. Sci.,46 (1986), 1–122. · Zbl 0636.68104
[6] Courcelle, B., Recognizability and 2nd order definability for sets of finite graphs, Research Report 8634, Bordeaux I University, 1986.
[7] Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars,Theoret. Comput. Sci.,55 (1988) (to appear). · Zbl 0644.68096
[8] Courcelle, B., A representation of graphs by algebraic expressions and its use for graph rewriting systems,Proc. 3rd International Workshop on Graph Grammars, Warrenton, Virginia, 1986 (to appear in 1987 in Lecture Notes Comput. Sci, Springer-Verlag, Berlin,). · Zbl 0643.68104
[9] Courcelle, B., On some sets of countable graphs having a decidable monadic second-order theory, Research Report 8729, Bordeaux I University, 1987. · Zbl 0643.68105
[10] Ehrig, H., Introduction to the algebraic theory of graphs, inProc. 1st International Workshop on Graph Grammars, Lecture Notes Comput. Sci., Vol. 73, Springer-Verlag, Berlin, 1979, pp. 1–69.
[11] Ehrig, H., and Kreowski, H. J., Push-out properties: an analysis of gluing constructions for graphs,Math. Nachr.,91 (1979), 135–149. · Zbl 0431.68069
[12] Ehrig, H., Kreowski, H. J., Maggiolo-Schettini, A., Rosen, B. R., and Winkowski, J., Transformations of structures: an algebraic approach,Math. Systems Theory,14 (1981), 305–334. · Zbl 0491.68035
[13] Ehrig, H., and Mahr, B.,Fundamentals of Algebraic Specifications, EATCS Monographs, Vol. 6, Springer-Verlag, Berlin, 1985. · Zbl 0557.68013
[14] Ehrig, H., Pfender, M., and Schneider, H., Graph grammars: An algebraic approach,Proc. 14th IEEE Symp. on Switching and Automata Theory, Iowa City, 1973, pp. 167–180.
[15] Eilenberg, S., and Wright, J., Automata in general algebras,Inform. and control,11 (1967), 52–70. · Zbl 0175.27902
[16] Elgot, C., Monadic computation and iterative algebraic theories,Proc. Logic Colloq. 73, North Holland, Amsterdam, 1975, pp. 175–230. · Zbl 0327.02040
[17] Engelfriet, J., Schmidt, E., IO and OI,J. Comput. System Sci.,15 (1977), 328–353 and16 (1978), 67–99. · Zbl 0366.68053
[18] Ginsburg, S., and Rice, H., Two families of languages related to ALGOL,J. Assoc. Comput. Mach.,9 (1962), 350–371. · Zbl 0196.01803
[19] Goguen, J., Thatcher, J., Wagner, E., and Wright, J., Initial algebra semantics and continuous algebras,J. Assoc. Comput. Mach.,24 (1977), 68–95. · Zbl 0359.68018
[20] Habel, A., and Kreowski, H. J., On context-free graph languages generated by edge replacements, inProc. 2nd International Workshop on Graph Grammars, Lecture Notes Comput. Sci., Vol. 153, Springer-Verlag, Berlin, 1983, pp. 143–158.
[21] Habel, A., and Kreowski, H. J., Some structural aspects of hypergraph languages generated by hyperedge replacements, Preprint, October 1985 (a shortened version can be found in Lecture Notes Comput. Sci., Vol. 247, Springer-Verlag, Berlin, 1987, pp. 207–219).
[22] Huet, G., Confluent reduction: abstract propertiies and applications to term rewriting systems,J. Assoc. Comput. Mach.,27 (1980), 797–821. · Zbl 0458.68007
[23] Huet, G., and Oppen, D., Equations and rewrite rules, a survey, inFormal Languages, Perspectives and Open Problems (R. Book, ed.), Academic Press, New York, 1980.
[24] Janssens D., and Rozenberg, G., A survey of NLC grammars, inProc. CAAP’ 83, L’Aquila, Lecture Notes Comput. Sci., Vol 159, Springer-Verlag, Berlin, 1983, pp. 114–128.
[25] Jouannaud, J. P. (ed.),Rewriting Techniques and Applications (Colloquium held in Dijon, May 1985), Lecture Notes Comput. Sci., Vol. 202, Springer-Verlag, Berlin, 1985.
[26] Lescanne, P. (ed.),Proc. Second Conference on Rewriting Techniques and Applications, Bordeaux, May 1987, Lecture Notes Comput. Sci., Vol. 256, Springer-Verlag, Berlin, 1987.
[27] McLane, S.,Category Theory for the Working Mathematician, Springer-Verlag, Berlin, 1971.
[28] Manes, E.,Algebraic Theories, Springer-Verlag, Berlin, 1976. · Zbl 0353.18007
[29] Mezei, J., and Wright, J., Algebraic automata and context-free sets,Inform. and Control,11 (1967), 3–29. · Zbl 0155.34301
[30] Nagl, M., Bibliography on graph-rewriting systems (graph grammars), inProc. 2nd International Workshop on Graph Grammars, Lecture Notes Comput. Sci., Vol. 153, Springer-Verlag, Berlin, pp. 415–448.
[31] Petrov, S., Graph grammars and automata (survey),Automat. Remote Control,39 (1978), 1034–1050. · Zbl 0417.68063
[32] Raoult, J. C., On graph rewritings,Theoret. Comp. Sci.,32 (1984), 1–24. · Zbl 0551.68065
[33] Rosen, B., Deriving graphs from graphs by applying a production,Acta Inform.,4 (1975), 337–357. · Zbl 0306.68050
[34] Schmeck, H., Algebraic characterization of reducible flowcharts,J. Comput. System Sci.,27(2) (1983), 165–199. · Zbl 0532.68018
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.