Mon logo perso

Merci à Pascale Boudière
pour le logo ci-dessus.                                                                                                                                         Bruno Courcelle 2004

Bruno  Courcelle

Honorary member  of  Institut Universitaire  de France

Last Update:  May 2018
Email :                    Postal address : LaBRI, 351 Cours de la Libération, F-33405 Talence, Fax : +33 5 40 00 66 69.
Another email : brunocourk   AROBASE  gmail  DOT com

Facebook  is a dirty commercial  business  that sells  personal data,

practices censorship  and denounces its customers to police.

 Kill  Facebook!


Book :  B. Courcelle and J. Engelfriet, ( ) Graph structure and monadic second-order logic, a language theoretic approach, 728 pages, 9 chapters, preface by Maurice Nivat,

published by Cambridge University Press (June  2012)  :

  Errata and updates (September 2014) ; Chapter 1 : Overview ; A review in ACM SIGACT News 45 (3) September 2014.

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 (1991) 153-202

See the  list of my main publications for period 1987-1996, classified by topics.

publications listed on the DBLP servor  of University of Trier, Germany (Thanks to them).

Publications since 1995

For downloading some articles (PDF files).

NA means "not available" in electronic form.

Contact me for getting full texts of the others or reporting a dead link. 

Submissions and unpublished articles are in red.


Surveys and tutorials.

 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 logic, Chapter 5 of the "Handbook of graph grammars and computing by graph transformations, Vol. 1 : Foundations", G. Rozenberg ed., World Scientific (New-Jersey, London), 1997, pp. 313-400.

S5. Décompositions arborescentes, Book chapter in French, Chapter 6 of Graphes et Applications 2, J.-C. Fournier ed., Hermès-Lavoisier, Paris 2007, pp.195-231.

S6. Graph structure and monadic second-order logic, a language theoretic approach, (with J. Engelfriet), Cambridge University Press, 2012, See above.

S7. Graph structure and monadic second-order logic: Language theoretical aspects, Invited communication to ICALP 2008, Reykjavik, Iceland. Volume 1 of Proceedings,  Lec. Notes Comput. Sci. 5125 (2008) 1-13 . (Slides below, see IC41).

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 (Research papers)

M1. The monadic second-order logic of graphs IX: Machines and their behaviours, Theoretical Computer Science, 151 (1995) 125-162.
Note: I have proved Conjecture (4.2) with I. Walukiewicz (University of Warsaw). See paper M3 below.

 M2. The monadic second-order logic of graphs X: Linear orders, Theoretical Computer Science, 160 (1996) 87-143. Two conference papers are based on this one: "Monadic second-order Logic and linear orderings of finite structures", CSL'1994, Lec. Notes Comput. Sci. 933 (1995) 163-176 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 Williamsburg, USA, 1994, Lec. Notes Comput. Sci. 1073 (1996) 487-501.

 M3. Monadic second-order logic, graph coverings and unfoldings of transition systems. (with I. Walukiewicz, LaBRI) Annals of Pure and Applied Logic, 92 (1998) 35-62.

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 Second Order Logic, joint work with J.A. Makowsky and U. Rotics (Technion, Israel), Discrete Applied Mathematics 108 (2001) 23-52.

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".)

 M14. The evaluation of first-order substitution is monadic second-order compatible. With T. Knapik (University of La Réunion, France), Theoretical Computer Science, 281 (2002) 177-206. Special issue offered to Maurice Nivat.

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.

M16. Vertex-minors, monadic second-order logic and a conjecture by Seese, with Sang-il Oum (Princeton University), J. Comb. Theory B 97 (2007) 91-126,  Final version, July 2004-March 2006. (Has been presented at  OC19, IC22, see below)

M17. The monadic second-order logic of graphs XVI : Canonical Graph Decompositions, Logical Methods in Computer Science 2 (2006) 1-46, Article, This article is readable on line for free at

M18. The modular decomposition of countable graphs : Definition and construction in monadic second-order logic, with Christian Delhommé, Université de La Réunion. Theoretical Computer Science  394 (2008) 1-38.  (Abstract in the proceedings of CSL 2005, see C24 below).

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) See :   Logical Methods in Computer Science 6 (2:2) (2010) 1-28 . See

M21 . Monadic second-order definable graph orderings  (with A. Blumensath, Darmstadt, Germany) See:  Logical Methods in Computer Science  10 (2014)  1-36  (available from :  )

Graph grammars; formal languages (Research papers)

G1. Structural properties of context-free sets of graphs generated by vertex replacement, Information and Computation 116 (1995) 275-293.

 G2. Facial circuits of planar graphs and context-free languages, (with D. Lapoire), MFCS'98, Brno, Lec. Notes Comput. Sci. 1450 (1998) 616-624. (NA)

Universal algebra and applications to graphs (Research papers).

U1. Equivalent definitions of recognizability for sets of graphs of bounded tree-width with J. Lagergren (Stockholm), Mathematical Structures in Computer Science 6 (1996) 141-165.   (NA)

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, E. Grädel, T. Wilke eds., Amsterdam University Press, 2008, pp. 251-260.

Graph theory, combinatorics (Research papers)

T1. The obstructions of a minor-closed set of graphs defined by a context-free grammar, (with G. Sénizergues), Discrete Mathematics 182 (1998) 29-51. Preliminary version in "Graph Grammars and their applications to Computer Science", Proceedings of a workshop held in Williamsburg, USA, 1994, Lec. Notes Comput. Sci. 1073 (1996) 351-367.

 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.

 T4. Une axiomatisation au premier ordre des arrangements de pseudo-droites euclidiennes, (with F. Olive), Annales de l'Institut Fourier, (Université J. Fourier, Grenoble, France) 49 (1999) 883-903 ((This article is in the proceedings of a Symposium dedicated to F. Jaeger, Grenoble, 1998). or here.

 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

T7. Circle  graphs  and  Monadic Second-order logic.  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 : Preliminary version on  HAL : hal-00128622, 

T9. Graph operations characterizing rank-width. (with  M. Kanté, Clermont-Ferrand) :  Discrete Applied Mathematics 157 (4)  (2009) 627-640

T10. On the model-checking of monadic second-order formulas with edge set quantifications. Discrete Applied Mathematics  160 (2012) 866-887. Available from :

T11. Clique-width and edge contraction. Information Processing Letters, 114 (2014) 42-44, See HAL (hal-00838630) or ArXiv :

T12.  The atomic decomposition of strongly connected graphs. July 2013. Research Report.

T13. The common structure of the curves having a same Gauss word. Chapter 1 of the book Automata, Computation, Universality (A. Adamatzky ed.), Springer, 2015, pp.1-37;  Final version

T14. Several notions of rank-width for countable graphs, J. Combinatorial Theory B 123 (2017) 186-214. Initial submission available from :

T15. A characterisation of clique-width through nested partitions (with P. Heggernes, D. Meister, C. Papadopoulos, U. Rotics),
Discrete Applied Mathematics  187 (2015) 70-81. submitted version.

Regularity equals monadic second-order definability for quasi-trees. in Fields of Logic and Computation II, Lec. Notes Comput. Sci. 9300  (2015) 129-141. Research Report.

T17. From tree-decompositions to clique-width terms, Discrete Applied Mathematics, 248 (2018) 125-144 also:

T18. Algebraic and logical descriptions of generalized trees. Logical Methods in Computer Science, 13 (2017) Issue 3, Article 7.  (Open access on

On quasi-planar graphs : clique-width and logical description. 2018, Discrete Applied Mathematics, in press,

T20. Grammars and clique-width bounds from split decompositions.
Submitted for publication. 2018,

T21. Axiomatizations of betweenness in order-theoretic trees, 2019, Submitted.

Graph algorithms

A1  Compact forbidden-set routing, with A. Twigg (Cambridge, UK), September 2006, Proceedings STACS 2007, Lec. Notes. Comput. Sci. 4393 (2007) 37-48. Submitted extended abstract (longer than the version in the proceedings).

A2 Efficient First-Order Model-Checking using Short Labels, (with C. Gavoille, M.M. Kanté).  Extended abstract, Proceedings of Frontiers of Algorithms Workshop, June 2008, Changsha, China, Lec. Notes Comput. Sci. 5059 (2008) 159-170. (Slides : see below IC40).

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 Will not be published

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 : 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, (with Irène Durand), 5th Conference on Algebraic Informatics 2013, Porquerolles, France, Final version. Lec. Notes Comp. Sci. 8080 (2013) 211-222.

A11 Computation by fly-automata beyond monadic second-order logic, (with I. Durand), Theoretical Computer Science, 619 (2016) 32-67, See

A12 Fly-automata, model-checking and recognizability, (with I. Durand), September 2014, Proceedings of Frontiers of Recognizability  (CIRM Seminar, April 2014), HAL (hal-01065434) and  ArXiv:

A13 Model-checking with Fly-automata, in Encyclopedia of Algorithms, second edition., Springer.,  Ming-Yang Kao  ed., Chapitre 20, 2015, 978-3-642-27848-8. <10.1007/978-3-642-27848-8_692-1>., Final version.

A14 Fly-automata for checking monadic second-order properties of graphs of bounded tree-width, Electronic Notes in Discrete Mathematics 50 (2015) 3-8, presented at Conference LAGOS2015, Brazil, see C73. Long version.  Complete  article :  A15.

A15 Fly-automata for checking MSO2 graph properties. Discrete Applied Mathematics, 245 (2018) 236-252.  See or

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. Published  in a volume dedicated to the memory of Gilles Kahn :
From Semantics to Computer Science, Essays in Honour of Gilles Kahn, Y. Bertot et al.  eds., Cambridge University Press, 2009.

English translation of original article (by T. Veldhuizen, revised by B. Courcelle) : Chapter 8, pp. 164-179, with, as introduction:

B. Courcelle: Program semantics and infinite regular terms (Chapter 7), pp. 160-163.

New typing of an old paper.

Completions of ordered magmas
, with Jean-Claude Raoult (Université Rennes I),  Fundamenta Informaticae 3 (1980) 105-118.

Corrections and updates.

 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.

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.

Graph structure and MSO logic (see S6 above) Corrections and updates.

Communications to conferences (from July 1999).

 IC: Invited communication,  SC: Submitted communication,  OC: Organization of a workshop.


 IC1: RTA-99, Trento, July 1999:
Hierarchical graph decompositions defined by grammars and logical formulas. M11 for complete article.

 IC2: Mathematical Foundations of Informatics, Hanoi, october 1999:
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, Créteil, Février 2000:
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.

 SC4: Graph Transformations, Berlin, March 2000:
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.

 IC6: Journées d'Informatique de Metz, May 2000:
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,

 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 La Réunion, November 2000:
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, Brasilia, August 2001 :
Graphs, Trees and Monadic Second-Order Logic, Part I : Tutorial, Part II : Recent results and open problems.


 IC12: Conference FOSSACS in Grenoble, April 2002:
Semantical evaluations as monadic second-order compatible structure transformations. See M 14 for the complete article. Slides (.
doc file).

OC13: Organization  (with P. Weil) of a side workshop during the International Conference on Graph Transformation on October 11 and 12 in Barcelona.
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, Bêdlewo Conference Center, PolandOn a conjecture by D. Seese. See OC13 and M15.


IC 15 :  Journées Complexité, modèles finis et bases de données, 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 Polytechnique, 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 Seminar, May 23-28.
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, Bordeaux, September 17-18.
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 and Logic, Auckland, New Zealand, December 11-13.
Title of  lecture :  Graph Transformations and Logic.
Slides (pdf)

IC21 : Developments in Languages Theory 2004, Auckland , New Zealand, December 13-17.
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 its Applications, Taupo Lake, New Zealand, December 13-17.
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, la Complexité et les Modèles Finis, Fontainebleau, Mai
Title of lecture : Vertex-Minors, Monadic Second-order logic, polynomial algorithms and Seese's Conjecture.  Full article : see M16

C24 : Computer Science Logic, Oxford , August 2005

Title of lecture : The modular decomposition of countable graphs : Constructions in Monadic Second-Order Logic, (with Christian Delhommé, Université de La Réunion). Paper in the proceedings, Lec. Notes Comput. Sci. 3634 (2005) 325-338. Full article : see M18.

C25 : International Conference on Graph Theory, September 2005, Hyères, France.
Title of Lecture : Graph  decompositions  definable  in Monadic Second-order logic, Full article : see M17.


OC26 : Computer Science Logic 2006, Szeged, Organization of a workshop. September 2006

IC27 : International  Conference  on  Discrete  Mathematics (  Bangalore, India, December 2006 : 
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. See above T13.

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, Aachen, Germany : Compact forbidden-set routing, with A. Twigg, (Cambridge, UK), Final version : 15 pages (the version in proceedings is reduced to 12 pages). See A1 above for references.

C31 : Enumeration and Probabilistic Methods in Combinatorics, Barcelona, June ( :

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, Portland, USA, (, August.

Title : Forbidden set labelling in graphs. Extended abstract.

IC34 : Algorithms and Complexity in Durham, Third Workshop, Durham, England, September.

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

IC35 :  Fall School on Algorithmic Graph Structure Theory. Tutorial to be delivered at Schloss Blankensee, Berlin, 4-7th October  (organized by M. Grohe). 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. Aachen, December.

Title :  Monadic second-order logic and  recognizability. Slides.  The article in the proceedings is different ; see U4 above.


 OC37 : Marseille, CIRM,  See CFP :
Title: 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.

 IC38 :  Théorie des nombres et Combinatoire, Mahdia, Tunisia, May.
Algebraic and model theoretical descriptions of finite graphs. Slides

 C39 : Topological and Geometric Graph Theory, Paris, May 2008.
Title : Connectivity check in 3-connected planar graphs with obstacles, (with C. Gavoille, M.M. Kanté, A. Twigg).  Abstract. Slides.

C40 : Frontiers of Algorithmics Workshop 2008, Changsha, China, June 2008.
Title :  Efficient First-Order Model-Checking using Short Labels, (with C. Gavoille, M.M. Kanté).  Abstract.

IC41 : ICALP, July 2008, Reykjavik,
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 la Recherche, Organisation des journées et exposé :
Title: 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, Banff International Research Station for Mathematical 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, Warwick, 23-25 March. Abstract. Slides.
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, Tarragona, Spain, April 2-8 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 at the University of Athens, May 2009)

IC47 : CAI 2009 : 3rd  International Conference on Algebraic Informatics May 3rd International Conference, Thessaloniki, Greece, May 19 – 22. Slides. Abstract in LNCS 5725 (2009) 78-80.
Lecture : On several proofs of the Recognizability Theorem.

IC 48 : ESSLLI, Bordeaux, Slides.
Evening Lecture (July 21st)  : On context-free graph grammars.

IC 49 : EuroComb 2009, Bordeaux, Slides.
Lecture : Logical characterizations of graph hierarchies (and of many other things)


C 50 : Logical Approaches to Barriers in Computing and Complexity, Greifswald, Germany, February,  Slides.
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, Paris, March,
Communication : Syntactic Tools for Equivalence Problems.

C 52 :  3rd European Lisp Symposium, May 2010, Lisbon
Communication (with Irène Durand, LaBRI) : Verifying monadic second-order graph properties with tree automata ,  Final version.

OC 53 : Workshop on Logic, Combinatorics and Computation, Brno, August 2010.

OC 54 : Workshop on  Graph Decompositions and Applications, Marseille, CIRM, October  2010. See announcement

IC 55 : FST-TCS, Chennai, India, December 2010.
Special tree-width and the verification of monadic second-order properties. Extended abstract (proceedings). Slides.

IC 56  :  Tutorial presented  in Chennai, Bangalore (2010)  and Athens (2011). Part1 . Part2 . Part3.


IC 57 : Journées de Combinatoire de Bordeaux. Janvier.
Title : 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, Title : Undecidable extensions of MSO logic.

IC 59 : Reachability  Problems , Genova, Italy, 28-30 september:
Automata for Monadic Second-order model checking. Abstract (Lec. Notes Comput.  Sci. Vol. 6945)  Slides.

IC 60 : GROW, 27-29  October, in Korea:
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. Slides, Slides.

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, Bordeaux. :
Canonical graph decompositions.  Slides

IC 64 : Colloque de Mathématiques Franco-Vietnamien, Vietrnam, Hué, 20-24 August.
The verification of monadic second-order properties of structured graphs. Slides.

 C65 : Bordeaux Graph Workshop,  November.
Title: The atomic decomposition of strongly connected graphs.  Same slides as for   IC62.



 IC66 :  Dagsthul Seminar : Tree Transducers and Formal Methods, 5-8 May 2013.
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.
Title: 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.

Title: Model-checking by infinite fly-automata, (with Irène Durand), Final version. Lecture Notes in Computer Science 8080 (2013) 211-222.

IC69 : GROW, Santorin, Greece, October 9-11.
Title: Graph algorithms based on infinite automata: logical descriptions and usable constructions. Slides.


IC70 : FREC meeting in Marseille, March April 28-30,  CIRM.
Title: Recognizable sets of graphs : algebraic and logical aspects. Slides. See A12 for extended abstract.

C71 : Bordeaux Graph Workshop, November 19-22, Bordeaux
Title : Rank-width for countable graphs and compactness, Slides.


IC72 : Workshop on graph decompositions, CIRM, January.
Title : Comparing clique-width and tree-width for degree-constrained graphs. See complete article T17.

C73 : Latin-American Graphs and Optimization Symposium,  May, Brasil.
Title: Fly-automata for checking monadic second-order properties of graphs of bounded tree-width. Long version. Slides. Slides of a lecture in Fortaleza.

IC74: Workshop on enumeration, Leiden, The Netherlands, August.
Title : Enumeration algorithms based on fly-automata. Slides.


IC75 : Workshop on Enumeration (ANR project), Orléans, January.
Title : Computation and enumeration by fly-automata, (joint work with I. Durand), Slides.
More slides on Query evaluation by fly-automata : Labri seminar.

IC76 : Dagsthul workshop on graph polynomials, June.
Title :  Computations of monadic second-order polynomials by fly-automata. Slides.

C77 : Bordeaux Graph Workshop, November
Title : Descriptions of generalized trees by logic and algebraic terms. Complete article : T18.


IC78 : Shonan seminar on Logic and Computational Complexity, Japan, September.
Title : Tree-width, clique-width and fly-automata. Revised slides, see IC79.

IC79 : GROW, Toronto, Canada, October (Thanks to Fields Institute for wellcoming this workshop).
Title : Tree-width, clique-width and fly-automata. Slides. Lecture based on articles T17 and A15. See also next.
More slides  on Clique-width and tree-widthLabri  Seminar:


IC 80 : LaSH : Workshop on Logic and Search, FLOC, Oxford, July 18-19.
Title : Monadic second-order model checking with fly-automata, joint work with I. Durand. Slides

IC81 : 40 années d'algorithmique de graphes, Journées en l'honneur de Michel  Habib
Title : Monadic second-order model checking with fly-automata, joint work with I. Durand. Slides


IC 82 : Complexity and Algorithms, Roscoff, March.
    Verification of MSO properties with fly-automata. Slides : see next. Another lecture:
    Bounding clique-width by means of split-decompositions, for directed and undirected graphs. Slides

IC83 : Complexity and Model Theory, Moscow, June 9-11, Slides.

All comments are welcome (dead links in particular) :

Document made with KompoZer  (I recommend KompoZer).