

Merci à Pascale Boudière
(pascale.boudiere@ulysse.u-bordeaux.fr)
pour le logo ci-dessus.

Last Update August 9th 2010
Weather in
I am
co-organizing a workshop in
Logic,
Combinatorics
and Computation
in finite
and infinite structures
Satellite workshop of the
joint conferences
Mathematical Foundations of
Computer Science & Computer Science Logic
How to reach Labri from
Do you want to publish in French or English ? I am director of the series “Informatique et Mathématiques Discrètes” of
“Editions Publibook
Universitaire”. See
this page.
My own book in progress : Graph structure and monadic second-order logic
(See S6 below) All
comments are welcome.
Other links : Introduction to context-free languages (Lecture delivered in
Cours
de Master : Grammaires de graphes et Logique.
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
Email : courcell@labri.fr
Postal address : LaBRI, 351
Cours de
Publications
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.
See the general orientation of my current work. Version de ce texte en français.
My publications listed on the DBLP servor of
Submissions
and accepted but unpublished articles are in red.
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 logic,
Chapter 5 of the "Handbook of graph grammars and computing by graph
transformations, Vol. 1 : Foundations", G. Rozenberg
ed., World Scientific (New-Jersey,
S5. Décompositions arborescentes,
Book
chapter in French, Chapter 6 of Graphes et Applications 2, J.-C. Fournier ed., Hermès-Lavoisier,
S6. Graph structure and monadic second-order
logic, a language theoretic approach (Book in preparation, 10 chapters plus references in one big volume, to be
published by Cambridge University Press): Present
state of Part 1 : Chapters 1-6. Part 2 : Chapters 7-10 (Chapter 8 is by Joost
Engelfriet) For sparing trees,
do not print blindly. Comments welcome.
S7.
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, Volume 4, 2010, to appear.
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
(
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
M3. Monadic
second-order logic, graph coverings and unfoldings of
transition systems. (with
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 (
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 (
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 (
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 Delhommé,
Université de
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,
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,
U1.
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,
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
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 or from:
http://www.iicm.edu/.
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,
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.
Diagonal walks in plane graphs and local
duality, March 2006, Comments
welcome
T9.
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/.
T10. Graph operations characterizing
rank-width. (with M. Kanté,
T11. On the model-checking of
monadic second-order formulas with edge set quantifications. Submitted (May 2010). Available from : http://hal.archives-ouvertes.fr/hal-00481735/fr/
Graph
algorithms
A1 Compact
forbidden-set routing, with A. Twigg (
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,
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 labellings for efficient
first-order model-checking (with C. Gavoille and M. Kanté), November
2008. Final version. (Expanded version of A2). Available on the servor. DOI: 10.1007/s10878-009-9260-7
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.
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 :
From 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.
New typings of old
papers.
Completions of ordered magmas, with Jean-Claude Raoult (Université Rennes
I), Fundamenta Informaticae 3 (1980) 105-....
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,
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.
IC: Invited communication
SC: Submitted communication
OC: Organization of a workshop.
1999
IC1: RTA-99,
Hierarchical graph decompositions defined by grammars and logical formulas.
M11 for complete article.
IC2: Mathematical
Foundations of Informatics,
The monadic second-order logic of graphs: Tools from graph theory,
see M10 for complete paper.
2000
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,
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
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).
2001
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.
2002
IC12: Conference
FOSSACS in
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
Self-invited talk: On a conjecture by D. Seese. Slides for the
talk (Pdf).
2003
SC 14: Finite Model
Theory, March 31 to April 4, workshop,
2004
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,
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,
Title of lecture : Graph Transformations and Logic. Slides (pdf)
IC21 : Developments in Languages Theory
2004,
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,
Title of lecture : Vertex-Minors, Monadic Second-order logic, polynomial
algorithms and Seese's Conjecture. (cf. M16 ) Slides (pdf)
2005
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
Science Logic,
Title of lecture : The
modular decomposition of countable graphs : Constructions in Monadic
Second-Order Logic, joint work with Christian Delhommé
(Université de
C25 : International
Conference on Graph Theory, September 2005,
Title of Lecture : Graph decompositions definable in
Monadic Second-order logic, Full article : see M17.
2006
OC26 : Computer Science Logic 2006,
IC27 : International Conference on
Discrete Mathematics (http://www.ramanujanmathsociety.org/icdm2006.html)
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.
2007
C30 : Symposium on Theoretical Aspects of Computer Science, STACS 2007,
C31 : Enumeration and Probabilistic Methods in Combinatorics,
Title :
A multivariate graph polynomial
(see T9 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 Complexity in
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 :
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.
2008
OC37 : Marseille, CIRM, See CFP : http://www.lirmm.fr/~paul/ANR/cirm.html
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. See http://www.rogics.com/.
Slides
C39 : Topological
and Geometric Graph Theory,
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,
Title :
Efficient First-Order
Model-Checking using Short Labels, (with C. Gavoille,
M.M. Kanté). Abstract. Slides.
IC41 : ICALP, July 2008,
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.
2009
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. Slides-Part 1, Slides-Part2, Exercises, Abstract. (Also presented at
the
IC47 : CAI 2009 : 3rd
International Conference on Algebraic Informatics May 3rd
International Conference,
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)
2010
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 Computation,
OC 54 : Workshop
on Graph Decompositions and Applications,
Marseille, CIRM, October 2010. See
IC 55 : FST-TCS,