Facebook is a dirty commercial business
that sells personal data, practices censorship and denounces its customers to police. Kill Facebook! |
![]() |
Publications
Book :
B.
Courcelle and J.
Engelfriet, (engelfri@liacs.nl ) Graph structure
and monadic second-order logic, a language theoretic approach, 728 pages, 9 chapters, preface
by Maurice
Nivat,
published by
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.
My publications listed on the DBLP
servor
of
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, (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,
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
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 article is readable on line for free at https://lmcs.episciences.org/2250
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) See : http://hal.archives-ouvertes.fr:80/hal-00287223/fr Logical
Methods in Computer Science 6 (2:2)
(2010) 1-28 . See https://lmcs.episciences.org/1208
M21 . Monadic second-order definable graph orderings
(with A.
Blumensath, Darmstadt, Germany) See: http://hal.archives-ouvertes.fr/hal-00649990/fr/ Logical Methods in Computer Science 10 (2014) 1-36 (available from : https://lmcs.episciences.org/793 )
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.
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.
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. Final
Version. Journal of Applied
Logic
6 (2008) 416-442.
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/
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
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 : 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.
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: http://fr.arxiv.org/abs/1409.5368
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>. https://hal.archives-ouvertes.fr/hal-01299432, 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 https://arxiv.org/abs/1511.08605# or https://hal.archives-ouvertes.fr/hal-01234622
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.
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,
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.
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, (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)
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.
2007
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
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 :
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.
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.
Title: 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
Workshop 2008,
Title : Efficient
First-Order Model-Checking using Short Labels, (with C. Gavoille,
M.M.
Kanté). Abstract.
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
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,
Title: Comparing several proofs of
the Recognizability Theorem.
Updated slides : see IC47 below.
IC44 : Graph Minors,
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. See below IC56. 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 announcement
IC 55 : FST-TCS,
Title: Special tree-width and the
verification of monadic second-order properties. Extended abstract
(proceedings).
Slides.
IC 56 : Tutorial
presented in Chennai,
2011
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,
IC 59 : Reachability Problems ,
Title: Automata for Monadic
Second-order model checking. Abstract (Lec. Notes Comput. Sci. Vol. 6945)
Slides.
IC 60 : GROW, 27-29 October, in
Title: On the constructive power of
monadic second-order logic, Abstract, Slides.
2012
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
Title: Graph decompositions, graph
structure and algorithms,
June 2011. Slides.
IC63: Workshop on monadic second-order logic, 18-20 June 2012,
Title: Canonical graph
decompositions. Slides
IC 64 : Colloque
de Mathématiques Franco-Vietnamien,
Vietrnam, Hué, 20-24 August.
http://smf.emath.fr/content/congres-commun-smf-vms
Title:
2013
Title: 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.