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, London), 1997, pp. 313-400.
Disponible en format PDF (75 pages, ne pas tout imprimer)

http://www.labri.fr/Perso/~courcell/CoursMaster/GraphGrammarsBook(1997).pdf

R. Downey, M. Fellows : Parametrized complexity, Springer 1999.
(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