B. Courcelle,

Reference updates and corrections for the paper:

Graph rewriting : An algebraic and logic approach

Chapter 5 of "Handbook of Theoretical Computer Science, Volume B",
J. Van Leeuwen ed., Elsevier, 1990, pp.193-242.


page 201, line -5 -4, replace the sentence by the following:

If the strong perfect graph conjecture holds, then a graph is perfect iff it does not contain as induced subgraph an odd cycle with at least 5 vertices and its edge complement does not either; from this characterization, the perfectness of a graph can be expressed in MSOL.

page 205, Theorem 2.1 : Every finite hypergraph over B is denoted by some algebraic expression constructed over H(B).

page 210, middle : ....... the unique hypergraph homomorphism .....

page 220, line 4 (line (1) of Theorem 4.4) : read L(GAMMA) instead of L(G);

page 223, middle of line numbered by (4): replace the second E(H) by E(G).

page 224, middle of line numbered by (3): delete "loop-free" (paths do not go twice through a same vertex).

page 225, replace by the following the last sentence of Theorem 5.5:

Conversely, if L is context-free and is of the form FORB(K) for some finite set of graphs K , then K contains some planar graph.

Replace in the proof:

.... a sufficiently large grid Q.

by :

... a sufficiently large grid Q not in L. Then Q reduces by edge contractions and deletions to a graph in K . Being a minor of Q, this graph is planar.

(Theorem 5.5 is correct as stated; this is only a slight improvement.)

page 225, line -2:

...... forbidden minors, at least one of which is planar,

page 227: Proposition 6.3 is incorrect (it entails that P = NP). It should be restated as follows:

Let B' be a finite subset of B. Let phi be a closed monadic second-order formula in L(B,n). One can decide in time O(size(e)) whether the hypergraph defined by an expression e in FE(B)n satisfies phi.

One should replace in the proof B by B' .

page 229, before Proposition 7.1: FG instead of GF

page 229, line - 5: insert the following remark:

The notions of tree-decomposition and tree-width defined in Section 5 easily extend to infinite hypergraphs. The tree-width and the width of a hypergraph are linearly related (see [28]; Lemma 5.4 holds for finite and infinite graphs), so that in all statements of this section "width" can be replaced by "tree-width".

page 231, diagram of Lemma 7.6: Read Fw instead of fw.

page 235 : line 1 replace MSOL by MSOLf

Additions to Section 8: "Guide to the literature" (prepared in 1991 according to the current state-of-the art)

Under subheading "Section1"

page 235, line -18: Insert:

See Gurevich [Gu] for a survey on monadic second-order logic.

page 235, end of subsection, add:

The same properties of graphs, either of degree at most some fixed k or that do not contain some fixed graph as a minor, can be expressed in MSOL with or without quantifications on sets of edges [Cou2].

Monadic second-order logic can also be used to specify relations on graphs and hypergraphs, called monadic second-order transductions: see [29, Cou1, Cou2, Cou3, Cou4, CE, Eng2].

Under subheading "Section2"

page 235, between lines -11 and -12 insert:

Alternative (but in some sense equivalent) operations are defined in [ACPS, Cou3, Cou7].

page 236, end of subsection, add:

Van der Broek compares in [VDB] the single push-out approach of Raoult and the double push-out approach of Ehrig et al. The single pushout approach is developped in two papers by Loewe and Kennaway in [EKR].

Under subheading "Section3"

page 237, end of subsection, add the following paragraph:

Context-free graph and hypergraph grammars have been extensively investigated in the years 1989-1991. It follows that there are only two types of context-free sets of graphs and hypergraphs, the HR (Hyperedge Replacement ) ones, that are just called context-free in the chapter of the "Handbook", and the VR (Vertex Replacement) ones. The VR sets contain the Boundary NLC sets of graphs of [83,84], the Confluent NLC sets of graphs [21], the C-edNCE sets of graphs of [CER, Eng1, Eng2] and the Separated Handle-Rewriting sets ofhypergraphs of [CER]. See [ER] for a survey. Algebraic characterizations can be found in [CER, Cou3]. The classes HR and VR can be characterized in terms of monadic second-order definable transductions and recognizable sets of finite trees, independently of any rewriting mechanism by the results of [Eng2, CE]. It follows from these characterizations that HR sets are related to MSOL with quantifications on sets of edges like VR sets are to MSOL without such quantifications. The relations between the classes HR and VR are known from [42, Bra3, Cou5, CE, EH]. Every HR set of simple hypergraphs is VR and one can decide whether a VR set is HR ([Cou5]).

Under subheading "Section 5 "

page 238, end of subsection, add:

An important open problem is the effective construction of the forbidden minors for interesting minor closed sets of graphs. For an example, [5] is devoted to the determination of those of the class of graphs of tree-width at most 3, and the method used in this paper does not extend to other classes. This topic is the subject of [Cou6, FL1, FL2], but the main result is that of [LA], which gives an algorithm for determining the forbidden minors of graphs of tree-width at most k for every k. However, the algorithm is intractable, and the forbidden minors are not explicitely known, even for k = 4. (See recent work by Courcelle and Sénizergues.)

Under subheading "Section 6"

page 238, end of subsection, add:

Arnold and Crubille have shown in [AC] that each graph property expressible in a fragment of MSOL called the mu-calculus can be evaluated in linear time for every graph, not necessarly of bounded width.

Graph grammars, even context-free, are difficult to parse as we have seen. See also [Bra2]. Special classes with polynomial parsing algorithms have been considered in [64, BK, Bra1, Lag, Vog]. Linear time graph recognition algorithms based on graph rewriting systems are constructed effectively for sets of graphs that are both definable in MSOL and of bounded tree-width ([ACPS]).

Classes of functions on graphs evaluable in polynomial time on graphs generated by context-free graph grammars are defined in [BPT, CM, HR], by extending the idea of compatibility introduced in [21, 26, 50, 66] for graph properties.

New references and updates

The list below contains updates to original references (numbered with figures as in the Handbook) and new references, numbered with letters and figures.

[ACPS] ARNBORG S., COURCELLE B., PROSKUROWSKI A., SEESE D., An algebraic theory of graph reduction, JACM 40 (1993) 1134-1164.

[3] ARNBORG S., LAGERGREN J., SEESE D., Easy problems for tree-decomposable graphs, J. of Algorithms 12 (1991) 308-340.

[5] ARNBORG S.,, PROSKUROWSKI A., CORNEIL D., Forbidden minors characterization of partial 3-trees, Discrete Mathematics 80 (1990) 1-19.

[AC] ARNOLD A., CRUBILLE P., A linear algorithm to solve fixed point equations on transition systems, Inf. Proc. Letters 29 (1988) 57-66.

[8] BAUDERON M., Infinite hypergraphs I. Basic properties, Theor. Comput. Sci. 82 (1991) 177-214, and II. Systems of recursive equations, Theor. Comput. Sci. 103 (1992) 165-190.

[BK] BODLAENDER H., KLOKS T., Better algorithms for path-width and tree-width of graphs, Proceedings 18th ICALP, Lecture Notes in Computer Science 510 (1991) 544-555.

[BPT] BORIE R., PARKER R., TOVEY C., Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica 7 (1992) 555-581.

[Bra1] BRANDENBURG F.-J., On partially ordered graph grammars, in [39] pp.99-111.

[Bra2] BRANDENBURG F.-J., On polynomial time graph grammars, Lecture Notes in Computer Science 294 (1988) 227-236.

[Bra3] BRANDENBURG F.-J., The equivalence of boundary and confluent graph grammars on graph languages with bounded degree , Lecture Notes in Computer Science 488 (1991) 312-322.

[28] COURCELLE B., The monadic second-order logic of graphs III, Tree-decompositions, minors and complexity issues, Informatique Théorique et Applications, 26 (1992) 257-286.

[29] COURCELLE B., The monadic second-order logic of graphs IV, Definability properties of equational graphs, Annals Pure Applied Logic 49 (1990) 193-255.

[Cou1] COURCELLE B., The monadic second-order logic of graphs V: On closing the gap between definability and recognizability, Theoret. Comput. Sci. 80 (1991) 153-202

[Cou2] COURCELLE B., The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discrete Applied Mathematics, 54 (1994) 117-149. See corrections.

[Cou3] COURCELLE B., The monadic second order logic of graphs VII: Graphs as relational structures, Theoret. Comput. Sci., 101 (1992) 3-33.

[Cou4] COURCELLE B., Monadic-second order graph transductions: a survey, Theoret. Comput. Sci. 126 (1994) 53-75.

[Cou5] COURCELLE B., Structural properties of context-free sets of graphs generated by vertex-replacement, Information and Computation 116 (1995) 275-293.

[Cou6] COURCELLE B., On constructing obstruction sets of words, Bulletin of EATCS, Vol.44, June 1991, pp. 178-185.

[Cou7] COURCELLE B., Graph grammars, Monadic Second-order logic and the theory of graph minors, in "Graph Structure Theory", N. Robertson et P. Seymour eds., Contemporary Mathematics (Amer. Math. Soc.) 147 (1993) 565-590.

[CE] COURCELLE B., ENGELFRIET J., A logical characterization of the sets of hypergraphs generated by hyperedge replacement grammars, Mathematical System Theory 28 (1995) 515-552.

[CER] COURCELLE B., ENGELFRIET J., ROZENBERG G., Handle-rewriting hypergraph grammars, J. Computer System Sci. 46 (1993) 218-270.

[CM] COURCELLE B., MOSBAH M., Monadic second-order evaluations on tree-decomposable graphs, Theoret. Comput.Sci., 109 (1993) 49-82.

[EKR] EHRIG H., KREOWSKI H.-J., ROZENBERG G., Graph Grammars and their Applications to Computer Science, Fourth International Workshop , Lecture Notes in Computer Science 532 , 1991.

[Eng1] ENGELFRIET J., Context-free NCE graph grammars, Proc. FCT' 89, Lecture Notes in Computer Science 380 (1989) 148-161.

[Eng2] ENGELFRIET J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, in [EKR] pp. 311-327.

[EH] ENGELFRIET J., HEYKER L., Hypergraph languages of bounded degree, Research Report 91-01, University of Leiden, 1991.

[ER] ENGELFRIET J., ROZENBERG G., Graph grammars based on node rewriting: an introduction to NLC graph grammars, in [EKR] pp. 12-23.

[FL1] FELLOWS M., LANGSTON M., On search decision and the efficiency of polynomial time algorithms, Proceedings ACM-STOC 1989, pp. 501-512.

[FL2] FELLOWS M., LANGSTON M., An analogue of the Myhill-Nerode theorem and its use in computing finite basis characterizations, 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 520-525.

[Gu] GUREVICH Y., Monadic second-order theories, in "Model theoretic logic", J. Barwise and S. Feferman eds., Springer, Berlin, 1985, pp. 479-506.

[HR] HOHBERG W., REISCHUK R., A framework to design algorithms for optimization problems on graphs, Research Report, Technische Hochschule Darmstadt, Germany, October 1990.

[Lag] LAGERGREN J., Efficient parallel algorithms for tree-decomposition and related problems, Proceedings of IEEE Symp. on F.O.C.S., 1990, pp. 173-182.

[LA] LAGERGREN J., ARNBORG S., Finding minimal forbidden minors using a finite congruence, Proceedings 18th ICALP , Lecture Notes in Computer Science 510 (1991) 532-543.

[64] LAUTEMANN C., The complexity of graph languages generated by hyperedge replacement, Acta Informatica 27 (1990) 399-421.

[86] SEESE D., The structure of the models of decidable monadic theories of graphs, Annals of Pure Applied Logic 53 (1991) 169-195.

[VDB] VAN DEN BROEK M., Comparison of two graph rewrite systems, Theor. Comput. Sci. 61(1988) 67-82.

[VL] VAN LEEUWEN J., Graph algorithms in "Handbook of Theoretical Computer Science, Vol. A", J. Van Leeuwen ed., 1990, Elsevier, pp. 523-631.

[Vog] VOGLER W., Recognizing edge replacement graph languages in cubic time, in [EKR] pp. 676-687.

Return to main page.