Bruno Courcelle

Publications of years 1987-1996 classified by topics

Last update: January 2004
Recent works

Universal algebra and applications to trees and graphs.

[UA1] (with M.Bauderon), Graph expressions and graph rewritings, Mathematical Systems Theory 20 (1987) 83-127 (Presented at CAAP, 1986, Nice)

[UA2] On recognizable sets and tree automata , in "Resolution of equations in algebraic structures", M. Nivat, H. Ait-Kaci eds., Academic Press, 1989, 93-126.

[UA3] Recognizable sets of unrooted trees, in "Tree automata and Languages", M. Nivat , A. Podelski eds., Elsevier, 1992, pp.141-157

[UA4] Recognizable sets of graphs: Equivalent definitions and closure properties, Mathematical Structure in Computer Science 4 (1994) 127-138.

[UA5] (with J. Lagergren), Recognizable sets of graphs of bounded tree-width, Proceedings of a Dagstuhl seminar, January 1993, Lec. Notes Comp. Sci.776, 1994, pp.138-152.

[UA6] (with J. Lagergren) Equivalent definitions of recognizability for sets of graphs of bounded tree-width, Math. Structure in Comp. Sci. 6 (1996) 141-165.

[UA7] Basic notions of Universal Algebra for language theory and graph grammars, Theoret. Comp. Sci., "Tutorial section", 163 (1996) 1-54.

Graph grammars, graph rewriting

[GG1] An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoretical Computer Science 55 (1987) 141-181 (Presented at STACS, 1988, Bordeaux). See corrections.

[GG2] Graph rewriting : An algebraic and logic approach, in "Handbook of Theoretical Computer Science, Volume B", J. Van Leeuwen ed., Elsevier,1990, pp.193-242. See corrections and updates.

[GG3] Recursive queries and context-free graph grammars, Theoret. Comput. Sci. 78 (1991) 217-244.

[GG4] (with S.Arnborg, A. Proskurowski, D. Seese): An algebraic theory of graph reduction, JACM 40 (1993) 1134-1164, (Presented at International Workshop on Graph Grammars, Bremen, 1991, see Lec. Notes Comp. Sci. 532).

[GG5] (with J. Engelfriet, G. Rozenberg), Handle-rewriting hypergraph grammars, J. Computer System Sci. 46 (1993) 218-270.

[GG6] Structural properties of context-free sets of graphs generated by vertex-replacement, Information and Computation 116 (1995) 275-293. (Presented at FCT 1993, Lec. Notes Comp. Sci. 710).

[GG7] (with J. Engelfriet), A logical characterization of hypergraph languages generated by hyperedge replacement grammars, Mathematical System Theory 28 (1995) 515-552.

Monadic Second-order Logic

[MSG1] The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85 (1990) 12-75. (Presented at International Workshop on Graph Grammars, Warrenton, Virginia, 1986; see Lec. Notes Comp. Sci. 291)

[MSG2] The monadic second-order logic of graphs II: Infinite graphs of bounded width, Mathematical Systems Theory, 21(1989)187-221.

[MSG3] The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues, Inform. Théor. et Applications 26 (1992) 257-286 (Presented at WG'88, Amsterdam).

[MSG4] The monadic second-order logic of graphs IV, Definability properties of equational graphs, Annals Pure Applied Logic 49 (1990) 193-255 (presented at ICALP 1989, Stresa, Italy).

[MSG5] The monadic second-order logic of graphs V : On closing the gap between definability and recognizability, Theor. Comput. Sci. 80 (1991) 153-202 (Invited lecture to MFCS 1989, Prorabka Kozubnik, Poland).

[MSG6] The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discrete Applied Mathematics, 54 (1994) 117-149, (Presented at LICS, 1990, Philadelphia). See corrections.

[MSG7] The monadic second order logic of graphs VII: Graphs as relational structures, Theoretical Computer Science, 101 (1992)3-33. (Presented at International Workshop on Graph Grammars, Bremen, 1991)

[MSG8] The monadic second order logic of graphs VIII: Orientations, Annals of Pure Applied Logic 72 (1995) 103-143 (Presented at LICS, 1993, Montreal).

[MSG9] The monadic second order logic of graphs IX: Machines and their behaviours, Theoret. Comp. Sci. 151 (1995) 125-162.

[MSG10] The monadic second-order logic of graphs X: Linear orderings, Theoret. Comp. Sci., 160 (1996) 87-143. (Presented at CSL'94, Kazimierz, Poland, see Lec. Notes Comp. Sci. 933, and in a workshop on graph grammars, see "Graph Grammars and their applications to Computer Science", Lec. Notes Comput. Sci. 1073).

[MS1] Graphs and monadic second order logic : some open problems, invited paper ("The Logic in Computer Science Column" by Y. Gurevich), in "Bulletin of EATCS",n°49, February 1993.

[MS2] (with M. Mosbah), Monadic second-order evaluations of tree-decomposable graphs, Theoretical Computer Sci. 109 (1993) 49-82 (presented at International Workshop on Graph Grammar, Bordeaux, 1991).

[MS3] Monadic-second order graph transductions: a survey, (Invited Lecture at CAAP, 1992, Rennes), Theoret. Comput. Sci. 126 (1994) 53-75.

Graph Theory, Minors

[GT1] On constructing obstruction sets of words, Bulletin of EATCS n° 44, 1991, pp. 178-185

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

[GT3] (with Y. Métivier), Coverings and minors, application to local computations in graphs, European Journal of Combinatorics 5 (1994) 127-138.

[GT4] (with A.Pariès), Mineurs d'arbres avec racines, Informatique Théorique et Applications 29 (1995) 401-422.

Program schemes, language theory and other topics

[Z1] Fundamental properties of infinite trees, Theoret. Comput. Sci. 25 (1983), 69-95.

[Z2] Equivalences and transformations of regular systems. Applications to recursive program schemes and grammars, Theoret. Comput. Sci. 42 (1986), 1-122.

[Z3] (with P. Deransart) Proofs of partial correctness for attribute grammars, Information and Computation 78 (1988) 1-55.

[Z4] A note on the minimalization of tree automata, Proceedings of 26th Semester of Banach Center, Warsaw, 1989, pp.197-203.

[Z5] Recursive applicative program schemes, in "Handbook of Theoretical Computer Science, vol. B", Elsevier, 1990, pp.459-492.

[Z6] (with A.Podelski and D Niwinski), A geometrical view of the determinisation and minimisation of finite-state automata, Mathematical Systems Theory 24 (1991) 117-146.

[Z7] "Editor of": Logique et Informatique, une introduction, Actes l'Ecole de Printemps d'Informatique Théorique de Albi, INRIA, collection didactique, vol. 8, 1991