|Facebook is a dirty commercial business
that sells personal data,
practices censorship and denounces its customers to police.
Book : B. Courcelle and J. Engelfriet, (email@example.com ) Graph structure and monadic second-order logic, a language theoretic approach,
or http://www.cambridge.org/knowledge/discountpromotion?code=Courcelle20 for 20% discount. (728 pages, 9 chapters, preface by Maurice Nivat).Errata and updates ; Chapter 1 : Overview
Articles and book chapters
My best cited articles. Citations Laureate 2004. "La volupté des mathématiques".
7 of my articles are among the 100 most cited articles in the journal Theoretical Computer Science (counting done in July 2005). Here is the list :
14/100 : Fundamental properties of infinite trees, Vol. 25 (1983) 95-169
28/100 : An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Vol. 55 (1987) 141-181
42/100 : Attribute grammars and recursive program schemes I, Vol. 17 (1982) 163-191 (with P. Franchi-Zannettacci)
55/100 : Equivalences and transformations of regular systems—Applications to recursive program schemes and grammars, Vol. 42 (1986) 1-122
65/100 : Monadic second-order evaluations on tree-decomposable graphs, Vol. 109 (1993) 49-82 (with M. Mosbah)
78/100 : Attribute grammars and recursive program schemes II, Vol. 17 (1982) 235-257 (with P. Franchi-Zannettacci)
83/100 : Monadic second-order definable graph transductions: a survey, Vol. 126 (1994) 53-75
90/100 : The
monadic second-order logic of graphs V:
on closing the gap between definability and recognizability, Vol. 80
See the list of my main publications for period 1987-1996, classified by
See the general orientation of my current work. Version de ce texte en français.
My publications listed on the DBLP servor of
S1. Réécriture de graphes: orientation bibliographique (10 pages, in French, ps file). This paper had been prepared for the proceedings of the Spring school on rewriting (Odeillo, May 1993) as volume 909 of Lec. Notes Comput. Sci. series (1995). However, it has been refused by Springer Verlag because it is written in French.
S2. Basic notions of Universal Algebra for Language Theory and Graph Grammars, Theoretical Computer Science 163 (1996) 1-54. Abstract, introduction and additional references
S3. On the expression of graph properties in some fragments of monadic second-order logic, in "Descriptive complexity and finite models", N. Immerman and P. Kolaitis eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, vol. 31, 1997, pp. 33-62.
S4. The expression
of graph properties and graph transformations in monadic second-order
Chapter 5 of the "Handbook of graph grammars and computing by graph
transformations, Vol. 1 : Foundations", G. Rozenberg ed., World
arborescentes, Book chapter in French, Chapter
Graphes et Applications 2, J.-C. Fournier ed., Hermès-Lavoisier,
S6. Graph structure and monadic second-order logic, a language theoretic approach, (with J. Engelfriet), Cambridge University Press, 2012, See above.
Graph structure and monadic second-order
logic: Language theoretical aspects, Invited
communication to ICALP 2008,
S8. Structuration des graphes et logique, in Leçons de Mathématiques d’Aujourd’hui, Collection Le sel et le fer, Vol. 4, Editions Cassini, Paris 2010, pp. 167-194, also here
monadic second-order logic of graphs IX: Machines and their behaviours,
Computer Science, 151 (1995) 125-162.
Note: I have proved Conjecture (4.2) with I. Walukiewicz (
M2. The monadic
second-order logic of graphs X: Linear orders, Theoretical
Science, 160 (1996) 87-143. Two conference papers are based on
"Monadic second-order Logic and linear orderings of finite
structures", CSL'1994, Lec. Notes Comput. Sci. 933 (1995)
and "The definition in Monadic Second-Order Logic of modular
decompositions of ordered graphs", in "Graph grammars and their
applications to computer science", Proceedings of a workshop held in
second-order logic, graph coverings and unfoldings of transition systems.
M4. The monadic second-order logic of graphs XI: Hierarchical decompositions of connected graphs, Theoret. Comput. Sci. 224 (1999) 35-58.
M5. The monadic second-order logic of graphs XII: Planar graphs and planar maps.Theoret. Comput.Sci. 237 (2000) 1-32.
M6. Linear time solvable optimization problems on certain graph families, joint work with J.A. Makowsky and U. Rotics (Technion, Israel), Proceedings of WG'98, 24rd International Workshop on Graph-Theoretic Concepts in Computer Science, Lec. Notes Comput. Sci. 1517 (1999) 1-16. (NA)
M7. On the Fixed
Parameter Complexity of Graph Enumeration Problems Definable in Monadic
Order Logic, joint work with J.A. Makowsky
and U. Rotics (
M8. Linear time solvable optimization problems on certain structured graph families, joint work with J. Makowsky and U. Rotics (Technion, Haifa, Israel). Theory of Computer Science (formerly Mathematical Systems Theory) 33 (2000) 125-150.
M9. The monadic second-order logic of graphs XIII: Graph drawings with edge crossings.Theoretical Computer Science, 244 (2000) 63-94.
M10. The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications. Theoretical Computer Science 299 (2003) 1-36.
M11. A monadic second-order definition of the structure of convex hypergraphs, Information and Computation 178 (2002) 391-411,
M12. Fusion in relational structures and the verification of monadic second-order properties, with J.A. Makowsky. Maths Structures in Computer Science 12 (2002) 203-235.
M13. Query efficient implementations of graphs of bounded clique-width, with R. Vanicat, Discrete Applied Mathematics 131 (2003) 129-150. (This article has been selected for inclusion in a special volume of Discrete Applied Mathematics : "Editor's Choice, Edition 2003".)
evaluation of first-order substitution is monadic second-order
With T. Knapik (
M15. The monadic second-order logic of graphs XV : On a conjecture by D. Seese. Journal of Applied Logic 4 (2006) 79-114, Revised version, March 2005. Sections of the initial version (April 2004) not retained in the final one.
monadic second-order logic and a conjecture by Seese, with Sang-il
M17. The monadic second-order logic of graphs XVI : Canonical Graph Decompositions, Logical Methods in Computer Science 2 (2006) 1-46, Article, This journal is readable on line for free at http://www.lmcs-online.org.
M18. The modular decomposition of countable
graphs : Definition and
construction in monadic second-order logic, with Christian
M19. Linear delay enumeration and monadic second-order logic, March 2006, Final Version, March 2007 Discrete Applied Mathematics 157 (2009) 2675-2700.
M20. On the monadic second-order transduction hierarchy (with A. Blumensath, LIAFA, Paris) See : http://hal.archives-ouvertes.fr:80/hal-00287223/fr Logical Methods in Computer Science 6 (2:2) (2010) 1-28.
M21 . Monadic second-order definable graph orderings (with A. Blumensath, LIAFA, Paris) See: http://hal.archives-ouvertes.fr/hal-00649990/fr/ Submitted for publication.
G1. Structural properties of context-free sets of graphs generated by vertex replacement, Information and Computation 116 (1995) 275-293.
circuits of planar graphs and context-free languages, (with D.
Equivalent definitions of recognizability for sets of graphs of bounded
tree-width with J. Lagergren (
U2. The recognizability of sets of graphs is a robust property with Pascal Weil, Theoretical Computer Science 342 (2005) 173-228. Slides of lecture.
U3. Recognizability, hypergraph operations and logical types with Achim Blumensath, Information and Computation 204 (2006) 853-919. Final version. Slides of lecture.U4. Quantifier-free definable graph operations preserving recognizability, in : Logic and Automata, History and Perspectives, J. Flum,
obstructions of a minor-closed set of graphs defined by a context-free
(with G. Sénizergues), Discrete Mathematics 182 (1998) 29-51.
Preliminary version in "Graph Grammars and their applications to
Science", Proceedings of a workshop held in
T2. A note on the computability of graph minor obstruction sets for monadic second-order ideals, (with R. Downey and M. Fellows), J.UCS, Vol.3, no 11(1997)1194-1198. This is an electronic journal: the paper can be obtained here.
T3. Upper bounds to the clique-width of graphs, joint work with S. Olariu (Old Dominion University, Norfolk, Virginia), Discrete Applied Mathematics 101 (2000) 77-114.
axiomatisation au premier ordre des arrangements de pseudo-droites
(with F. Olive), Annales de l'Institut Fourier, (Université J. Fourier,
T5. Clique-width of countable graphs: a compactness property. Discrete Mathematics 276 (2004) 127-148.
T6. Map genus, forbidden maps and monadic second-order logic, with V.Dussaux, The Electronic Journal of Combinatorics 9 (1) (2002), R40. (See http://www.combinatorics.org/Volume_9/Abstracts/v9i1r40.html).
T7. Circle graphs and Monadic Second-order logic, June 2005, Revised April 2007, Final Version. Journal of Applied Logic 6 (2008) 416-442.T8. A multivariate interlace polynomial and its computation for graphs of bounded clique-width, The Electronic Journal of Combinatorics 15 (1) (2008), R69. Readable on-line : http://www.combinatorics.org Preliminary version on HAL : hal-00128622, http://hal.archives-ouvertes.fr/.
Graph operations characterizing
rank-width. (with M. Kanté,
T10. On the model-checking of monadic second-order formulas with edge set quantifications. Discrete Applied Mathematics 160 (2012) 866-887. Available from : http://hal.archives-ouvertes.fr/hal-00481735/fr/T11. The atomic decomposition of strongly connected graphs and application to Gauss words. May 2012.Submitted (July 2012).
forbidden-set routing, with A. Twigg (
A2 Efficient First-Order
Model-Checking using Short Labels, (with C.
Gavoille, M.M. Kanté). Extended abstract,
Frontiers of Algorithms Workshop, June 2008,
A3 Constraint-path labellings on graphs of bounded clique-width (with A. Twigg), Theory of Computer Systems, 47 (2) (2010) 531-567. Final version. (expanded version of A1).
A4 Compact labelings for efficient first-order model-checking (with C. Gavoille and M. Kanté), J. of Combinatorial Optimization 21 (2011) 19-46. Final version. (Expanded version of A2).
A5 Optimal Labelling for Connectivity Checking in Planar Networks with Obstacles, (with C. Gavoille, M. Kanté, A. Twigg), March 2009. Submitted
A6 Verifying monadic second-order graph properties with tree automata (with Irène Durand, LaBRI), European Lisp Symposium, May 2010, Final version.
A7 Fly-automata, their properties and applications (with Irène Durand), 16th Int. Conf. on Implementation and Application of Automata, Lecture Notes in Computer Science 6807 (2011) 264—272. Final version
A8 Automata for the verification of monadic second-order graph properties (with Irène Durand), J. Applied Logic 10 (2012) 368-409. See : http://hal.archives-ouvertes.fr/hal-00611853/fr/ for the final version.
A9 Infinite transducers on terms denoting graphs, (with Irène Durand), European Lisp Symposium 2013, Madrid, Final version.
A10 Model-checking by infinite fly-automata
A10 Model-checking by infinite fly-automata, (with Irène Durand), 5th Conference on Algebraic Informatics 2013, Porquerolles, France, Final version.
A11 Computation by fly-automata beyond monadic second-order logic
A11 Computation by fly-automata beyond monadic second-order logic, (with Irène Durand), In preparation, Current version.
A translation from French of an "historical paper".
Algorithms for equivalence and
reduction to minimal form for a class of simple recursive equations,
with G. Kahn and J. Vuillemin, ICALP 1974, Saarbrücken.
Translation from French by T. Veldhuizen with original text, a few comments and additional references.
To appear in a volume dedicated to the memory of Gilles Kahn :
Semantics to Computer Science,
Essays in Honour of Gilles Kahn,
Y. Bertot et al. eds.,
English translation of original article (by T. Veldhuizen, revised by B. Courcelle) : Chapter 8, pp. 164-179, with an introduction
Program semantics and infinite regular terms (Chapter 7), pp. 160-163.
typings of old papers.
Completions of ordered magmas, with Jean-Claude Raoult (Université Rennes I), Fundamenta Informaticae 3 (1980) 105-....
Corrections and updates.
definition of context-free rewriting and its application to NLC graph
Theoretical Computer Science 55 (1987) 141-181 (Presented at STACS,
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.
A software for checking recursive definitions of graph polynomials (similar to the Interlace Polynomial ; needs JAVA) :http://www.labri.fr/perso/courcell/pdp/pdp.html
IC: Invited communication
SC: Submitted communication
OC: Organization of a workshop.
Hierarchical graph decompositions defined by grammars and logical formulas. M11 for complete article.
Foundations of Informatics,
The monadic second-order logic of graphs: Tools from graph theory, see M10 for complete paper.
SC3: Théorie des modèles finis et Bases de Données,
Opérations sur les graphes et les structures relationnelles: Fusions de sommets, complémentation d'arcs et Logique du Second-Ordre Monadique, (avec J. Makowsky, Haïfa, Israël), M12 for complete article.
Operations on Relational Structures and their compatibility with Monadic Second-Order Logic, (with J. Makowsky, Haïfa, Israël), see M12 for complete article.
IC5: Finite Model Theory,
CIRM, April 2000:
Sparse graphs and removal of edge set quantifications in monadic second order formulas, M12 for complete article.
Clique-width, monadic second order logic and efficient algorithms, M13 for complete article.
IC7: Théorie des
relations; colloque en l'honneur de R. Fraïssé, CIRM, May 2000:
Modular decompositions of graphs and hypergraphs, and their definitions by monadic second-order formulas, Abstract.
IC8: Fixed Points
in Computer Science, Paris, July 2000:
Least Fixed-Points, Graph Grammars and Monadic Second-Order Logic.
SC9: International Conference
of Graph Theory, Marseille, August 2000:
Clique-width of countable graphs: a compactness property. See T5 for complete article.
IC10: Logic for
Programming and Automated Reasoning, Ile de
Graph operations and monadic second-order logic: a survey, in 7th Conference LPAR, Lec. Notes Comput. Sci. 1955 (2000) 20-24 (extended abstract). (pdf file).
IC11: 8th Workshop
on Logic, Language, Information and Computation,
Graphs, Trees and Monadic Second-Order Logic, Part I : Tutorial, Part II : Recent results and open problems.
Semantical evaluations as monadic second-order compatible structure transformations. See M 14 for the complete article. Slides (.doc file).
(with P. Weil) of a side workshop during the International
Graph Transformation on October 11 and
Self-invited talk: On a conjecture by D. Seese. Slides for the talk (Pdf).
SC 14: Finite Model
Theory, March 31 to April 4, workshop,
IC 15 : Journées Complexité, modèles finis et bases de
Lausanne, May 14-15.
Title of lecture : Recent advances on a conjecture by D. Seese. See M15.
IC16 : Journées Mathématiques X-UPS, Ecole
Paris, May 17-18.
Title of lectures : Théorie des graphes : Définitions, applications et techniques de preuves (I) et (II). Survey.
IC17 : Robust and
approximative algorithms on particular classes of graphs, Dagsthul
Title of lecture : Monadic Second-order queries on graphs of bounded clique-width. Based on M13 and M15.
SC18 : Colloquium of the Research Training Network GAMES,
Title : Recognizability and Hypergraph operations using local informations (joint work with Achim Blumensath). See U3.
OC19 : Organization
of a side workshop about
Logic, graph transformations and finite and infinite structures,
during the International Conference on Graph Transformation on October 1-2, Roma.
Title of lecture : Isotropic systems, monadic second-order definition of vertex-minors and Seese’s Conjecture. (cf. M16 )
IC20 : International Workshop on Automata, Structures
Title of lecture : Graph Transformations and Logic. Slides (pdf)
IC21 : Developments in Languages Theory
Title of lecture : Recognizable sets of graphs, hypergraphs and relational structures : a survey. Slides (pdf). Overview published in the Proceedings. Lec. Notes Comput. Sci. 3340 (2004) 1-11.
IC22 : Combinatorics and
Title of lecture : Vertex-Minors, Monadic Second-order logic, polynomial algorithms and Seese's Conjecture. (cf. M16 ) Slides (pdf)
IC23 : Journées sur les Arithmétiques Faibles,
Title of lecture : Vertex-Minors, Monadic Second-order logic, polynomial algorithms and Seese's Conjecture. Full article : see M16
C24 : Computer
Title of lecture : The
modular decomposition of countable graphs : Constructions in Monadic
Second-Order Logic, joint work with Christian Delhommé
C25 : International
Conference on Graph Theory, September 2005,
Title of Lecture : Graph decompositions definable in Monadic Second-order logic, Full article : see M17.
OC26 : Computer Science
IC27 : International Conference on
Title : Graph equivalences and decompositions definable in Monadic Second order logic, Extended Abstract, Slides of the lecture (pdf)
IC28 : International Conference on Number Theory and Combinatorics, Srinivasa Ramanujan Centre, Kumbakonam, Inde, December 2006.
Title : Diagonal walks on plane graphs, Gauss words and local duality, Slides of the lecture.
S29 : Survey seminar presented in Chennai, December 2006 : Graph structuring and monadic second-order logic, Slides.
C30 : Symposium on
Theoretical Aspects of Computer Science, STACS 2007,
C31 : Enumeration and
Probabilistic Methods in Combinatorics,
Title : A multivariate graph polynomial (see T8 above ; slides of lecture).
C32 : WG 2007 (Graph Theoretic Concepts in Computer Science)
Communication : Graph operations characterizing rank-width and balanced graph expressions, with M. Kanté (LaBRI). Slides ; Proceedings June.
C33 : LOCALITY 2007,
side workshop of PODC 2007,
Title : Forbidden set labelling in graphs. Extended abstract.
IC34 : Algorithms and
Title : Monadic second-order queries on graphs : Vertex labelling for efficient evaluation and linear delay enumeration. Proceedings edited by H. Broesma et al., Texts in Algorithmics 9, College Publications, London, 2007 (ISBN 978-1-904987-55-0) pp. 3-12. Slides of lecture
Slides (53 pages). Exercises. Notes written by F. Breuer, H. Dell, B. Laubner, R. Urner (23 pages, thanks to them).
IC36 : Workshop on Automata and Logic, for W.Thomas’ 60th birthday.
Title : Monadic second-order logic and recognizability. Slides. The article in the proceedings is different ; see U4 above.
Labelling Schemes for solving First-Order and Monadic Second-Order Queries in Graphs not necessarily of bounded clique-width.
Short title : Verification of graph properties using short labels. Slides.
Algebraic and model theoretical descriptions of finite graphs. Slides
Title : Connectivity check in 3-connected planar graphs with obstacles, (with C. Gavoille, M.M. Kanté, A. Twigg). Abstract. Slides.
C40 : Frontiers of Algorithmics
Title : Efficient First-Order Model-Checking using Short Labels, (with C. Gavoille, M.M. Kanté). Abstract.
IC41 : ICALP, July
Title : Graph structure and monadic second-order logic : Language theoretical aspects. Communication : see S7 above. Slides. Abstract : LNCS 5125 (2008) 1-13.
OC42 : Journées des projets
GRAAL et ENUM de l’Agence Nationale pour
Différentes preuves du Théorème de Reconnaissabilité. Bordeaux, 3-5 septembre. (Slides see IC43).
IC43 : Symposium in the honor of J. Makowsky, Bertinoro, September 15th,
Comparing several proofs of the Recognizability Theorem. Updated slides : see IC47 below.
IC44 : Graph Minors,
Innovation and Discovery (BIRS) September 28-October3,
Lecture : Graph transformations expressed in logic and applications to structural graph theory, Slides.
IC45 : DIMAP workshop on
Algorithmic Graph Theory,
Lecture : Short vertex labels for connectivity checking in planar graphs with forbidden parts
IC46 : LATA
2009 : 3rd Intern. Conf. On Languages, Automata
Theory and Applications,
http://grammars.grlmc.com/LATA2009/. Abstract in LNCS 5457 (2009) 19-22.
Tutorial : Monadic
Second-Order Logic for Graphs :
Algorithmic and Language Theoretical Applications. See below IC56. Exercises, Abstract. (Also presented
IC47 : CAI 2009 : 3rd
International Conference on Algebraic Informatics May 3rd
Lecture : On several proofs of the Recognizability Theorem.
IC 48 : ESSLLI,
Evening Lecture (July 21st) : On context-free graph grammars.
IC 49 : EuroComb 2009,
Lecture : Logical characterizations of graph hierarchies (and of many other things)
C 50 : Logical Approaches
to Barriers in Computing and Complexity,
Communication (with Irène Durand, Labri) : Tractable constructions of finite automata from monadic second-order formulas.
IC 51 : Workshop on
Higher-Order Recursion Schemes
& Pushdown Automata,
Communication : Syntactic Tools for Equivalence Problems.
C 52 : 3rd
European Lisp Symposium, May 2010,
Communication (with Irène Durand, LaBRI) : Verifying monadic second-order graph properties with tree automata , Final version.
OC 53 : Workshop
on Logic, Combinatorics and
OC 54 : Workshop on Graph Decompositions and Applications, Marseille, CIRM, October 2010. See announcement
IC 55 : FST-TCS,
Special tree-width and the verification of monadic second-order properties. Extended abstract (proceedings). Slides.
IC 56 : Tutorial
presented in Chennai,
IC 57 : Journées de Combinatoire de Bordeaux. Janvier.
Sur l’expression des polynomes associés aux graphes en logique du second-ordre monadique. Slides in English.
C 58: Trentièmes Journées sur les Arithmétiques Faibles, Paris, June 2011. Slides
IC 59 : Reachability Problems ,
Automata for Monadic Second-order model checking. Abstract (Lec. Notes Comput. Sci. Vol. 6945) Slides.
IC 60 : GROW, 27-29 October, in
On the constructive power of monadic second-order logic, Abstract, Slides.
IC61 : Two seminar lectures in Hanoï, May 2012, at Institute of Mathematics of Vietnam and Institut Francophone d’Informatique.
IC 62: Dagstuhl Seminar : Data Reduction and Problem Kernels
Graph decompositions, graph structure and algorithms, June 2011. Slides.
IC63: Workshop on Monadic
Second-order logic, 18-20 June 2012,
Canonical graph decompositions. Slides
IC 64 : Colloque de Mathématiques Franco-Vietnamien, Vietrnam, Hué, 20-24 August.
Monadic second-order transductions of words and terms, based on works by J. Engelfriet and his coauthors. Slides.
IC67 : Durham workshop on graphs and application, UK, July 15-25.
Automata based graph algorithms for logically defined problems (3 lectures). Slides: Part 1, Part 2, Part 3, Supplement
C68 : 5-th Conference on Algebraic Informatics, Porquerolles, France, September 3-6.
Model-checking by infinite fly-automata, (with Irène Durand), Final version to appear in Lecture Notes in Computer Science.