Reference updates and corrections for the paper:

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 **hyper**graph 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**

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.

[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.