Structurations
des Graphes et Logique du
Second-ordre Monadique
Références
B. Courcelle : Décompositions arborescentes, Version préliminaire d’un chapitre d’ouvrage en cours de publication. 2006.
http://www.labri.fr/Perso/~courcell/CoursMaster/DecsArbosVersLongue.pdf
H.
Bodlaender : nombreux travaux sur la largeur arborescente (tree-width) :
http://www.cs.uu.nl/research/techreps/aut/hansb.html
B. Courcelle, S. Olariu :
Upper bounds to the clique-width of graphs, Discrete Applied Mathematics 101
(2000) 77-114.
http://www.labri.fr/Perso/~courcell/CoursMaster/BC-Olariu(2000).pdf
Une encyclopédie en ligne des classes de graphes : inclusions des classes,
largeur arborescente,
largeur de clique, complexité de la reconnaissance. (Nécessite Java)
http://wwwteo.informatik.uni-rostock.de/isgci
B. Courcelle : Basic notions
of Universal Algebra for Language Theory and Graph Grammars, Theoretical
Computer Science 163 (1996) 1-54. Disponible
en format pdf
http://www.labri.fr/Perso/~courcell/CoursMaster/UnivAlgGraphGramm(1996).pdf
B. Courcelle : 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,
Disponible en format PDF (75 pages, ne pas tout imprimer)
http://www.labri.fr/Perso/~courcell/CoursMaster/GraphGrammarsBook(1997).pdf
R.
(Cet ouvrage comporte plusieurs chapitres
sur les décompositions arborescentes, les mineurs, les théorèmes de Robertson
et Seymour).
J. Flum, M. Grohe :
Theory of parametrized complexity, Springer 2006.
Tree Automata Techniques and Applications
(TATA), ouvrage collectif en ligne sur les automates d'arbres (c'est-à-dire de
termes).
http://www.grappa.univ-lille3.fr/tata/
Références relatives à
la logique du second-ordre monadique (compléments, hors du programme de 2006-2007) :
J. Makowsky : Algorithmic applications of Fefermann-Vaught theorems.
Annals
Pure Applied Logic,
http://www.labri.fr/Perso/~courcell/CoursMaster/MakowskyFV.pdf
B. Courcelle, M. Mosbah, Monadic second-order evaluations of tree-decomposable
graphs, Theoretical Computer Sci. 109 (1993) 49-82.
B. Courcelle, J.A. Makowsky and U. Rotics, On the Fixed Parameter Complexity of
Graph Enumeration Problems Definable in Monadic Second Order Logic,
Discrete Applied Mathematics 108 (2001) 23-52.
http://www.labri.fr/Perso/~courcell/CoursMaster/CMR-Dam.pdf
B. Courcelle, R. Vanicat, Query efficient implementations of graphs of bounded
clique-width, with R. Vanicat, Discrete Applied Mathematics 131 (2003) 129-150.
http://www.labri.fr/Perso/~courcell/CoursMaster/BC-Vanicat.pdf
M. Frick, M. Grohe, The complexity of first-order and monadic second-order
logic revisited, Annals of Pure and Applied Logic, Volume 130 (2004)
3-31.
http://www.labri.fr/Perso/~courcell/CoursMaster/FrickGrohe.pdf
Exercices et problèmes
B. Courcelle
courcell@labri.fr
Mis à jour septembre 2010