Skip to Main content
Number of documents

58

Publications by Bruno Courcelle


Journal articles31 documents

  • Bruno Courcelle. Grammars and clique-width bounds from split decompositions. Discrete Applied Mathematics, Elsevier, In press, ⟨10.1016/j.dam.2019.07.001⟩. ⟨hal-02093211v2⟩
  • Bruno Courcelle. On quasi-planar graphs : clique-width and logical description. Discrete Applied Mathematics, Elsevier, 2018, ⟨10.1016/j.dam.2018.07.022⟩. ⟨hal-01735820v2⟩
  • Bruno Courcelle. From tree-decompositions to clique-width terms. Discrete Applied Mathematics, Elsevier, 2018. ⟨hal-01398972⟩
  • Bruno Courcelle. Several notions of rank-width for countable graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2017, 123, pp.186-214. ⟨hal-00957618⟩
  • Bruno Courcelle. Algebraic and logical descriptions of generalized trees. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2017, 13 (3), pp.Article 7. ⟨hal-01299077v3⟩
  • Bruno Courcelle, Irène Durand. Computations by fly-automata beyond monadic second-order logic. Theoretical Computer Science, Elsevier, 2016, 619, pp.32-67. ⟨hal-00828211v2⟩
  • Bruno Courcelle, Irène Durand. Computations by fly-automata beyond monadic second-order logic. TCS, 2016. ⟨hal-01757762⟩
  • Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics. A characterisation of clique-width through nested partitions. Discrete Applied Mathematics, Elsevier, 2015, 187, pp.70-81. ⟨hal-01022109⟩
  • Achim Blumensath, Bruno Courcelle. Monadic second-order definable graph orderings. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2014, 10 (1-2), pp.1-36. ⟨hal-00649990⟩
  • Bruno Courcelle. Clique-width and edge contraction. Information Processing Letters, Elsevier, 2014, 114 (1-2), pp.42-44. ⟨hal-00838630v2⟩
  • Bruno Courcelle. On the model-checking of monadic second-order formulas with edge set quantifications.. Discrete Applied Mathematics, Elsevier, 2012, 160, pp.866-887. ⟨10.1016/j.dam.2010.12.017⟩. ⟨hal-00481735v2⟩
  • Bruno Courcelle, Irène Durand. Automata for the verification of monadic second-order graph properties. Journal of Applied Logic, Elsevier, 2012, 10, pp.368-409. ⟨hal-00611853v2⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté. Compact Labelings For Efficient First-Order Model-Checking. Journal of Combinatorial Optimization, Springer Verlag, 2011, 21 (1), pp.19--46. ⟨hal-00342668⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté. Compact labelings for efficient first-order model-checking. J. Comb. Optim., 2011, 21, pp.19--46. ⟨10.1007/s10878-009-9260-7⟩. ⟨hal-02083537⟩
  • Achim Blumensath, Bruno Courcelle. On the monadic second-order transduction hierarchy. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2010, 6 (2), pp.1-28. ⟨hal-00287223v3⟩
  • Bruno Courcelle, Andrew Twigg. Constrained-path labellings on graphs of bounded clique-width. Theory of Computing Systems, Springer Verlag, 2010, 47, pp.531-567. ⟨hal-00512618⟩
  • Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics, Elsevier, 2009, 157, pp.2675-2700. ⟨10.1016/j.dam.2008.08.021⟩. ⟨hal-00333846⟩
  • Bruno Courcelle, Mamadou Moustapha Kanté. Graph operations characterizing rank-width. Discrete Applied Mathematics, Elsevier, 2009, 157, pp.627-640. ⟨10.1016/j.dam.2008.08.026⟩. ⟨hal-00334159⟩
  • Bruno Courcelle. A multivariate interlace polynomial. The Electronic Journal of Combinatorics, Open Journal Systems, 2008, 15 (1), pp.R69. ⟨hal-00128622v2⟩
  • Bruno Courcelle, Christian Delhommé. The modular decomposition of countable graphs. Definition and construction in monadic second-order logic. Theoretical Computer Science, Elsevier, 2008, 394 (1-2), pp.1-38. ⟨10.1016/j.tcs.2007.10.046⟩. ⟨hal-01186190⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté. Compact Labelings For Efficient First-Order Model-Checking. CoRR, 2008, abs/0811.4713. ⟨hal-02083559⟩
  • Bruno Courcelle, Christian Delhommé. The modular decomposition of countable graphs : Definition and construction in monadic second-order logic. Theoretical Computer Science, Elsevier, 2008, 394, pp.1-38. ⟨hal-00288222⟩
  • Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic, Elsevier, 2008, 6, pp.416-442. ⟨hal-00333840⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, Andrew Twigg. Connectivity check in 3-connected planar graphs with obstacles. Electronic Notes in Discrete Mathematics, Elsevier, 2008, 31, pp.151-155. ⟨10.1016/j.endm.2008.06.030⟩. ⟨hal-00333863⟩
  • Bruno Courcelle, Sang-Il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory, Series B, Elsevier, 2007, 97, pp.91-126. ⟨10.1016/j.jctb.2006.04.003⟩. ⟨hal-00334147⟩
  • Bruno Courcelle, Achim Blumensath. Recognizability, hypergraph operations, and logical types. Information and Computation, Elsevier, 2006, 204, pp.173-228. ⟨10.1016/j.ic.2005.11.006⟩. ⟨hal-00334149⟩
  • Bruno Courcelle. The monadic second-order logic of graphs XV : On a conjecture by D. Seese. Journal of Applied Logic, Elsevier, 2006, 4, pp.79-114. ⟨hal-00334050⟩
  • Bruno Courcelle. The monadic second-order logic of graphs XVI : Canonical graph decompositions. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2006, 2, pp.1-46. ⟨hal-00334069⟩
  • Bruno Courcelle, Pascal Weil. The recognizability of sets of graphs is a robust property. Theoretical Computer Science, Elsevier, 2005, 342, pp.173-228. ⟨hal-00096607⟩
  • Bruno Courcelle, Yves Métivier. Coverings and minors: application to local computations in graphs. European Journal of Combinatorics, Elsevier, 1994, 15, pp.127-138. ⟨hal-00332773⟩
  • Bruno Courcelle, Yves Métivier. Coverings and minors: application to local computations in graphs. European Journal of Combinatorics, Elsevier, 1994, 15, pp.127-138. ⟨hal-00307036⟩

Conference papers18 documents

  • Bruno Courcelle. Betweenness in order-theoretic trees. Journées sur les Arithmétiques Faibles, May 2020, Fontainebleau, France. ⟨hal-02497172⟩
  • Bruno Courcelle, Irène Durand. Infinite transducers on terms denoting graphs. European Lisp Symposium, Jun 2013, Madrid, Spain. pp.47-58. ⟨hal-00829088⟩
  • Bruno Courcelle, Irène Durand. Model-checking by infinite fly-automata. 5th Conference on Algebraic Informatics, Sep 2013, Porquerolles, France. pp.211-222. ⟨hal-00875114⟩
  • Bruno Courcelle, Irène Durand. Fly-automata, their properties and applications. 16th International Conference on Implementation and Application of Automata, Jul 2011, Blois, France. pp.264-272. ⟨hal-00588456⟩
  • Bruno Courcelle. Automata for Monadic Second-order model checking. Reachability Problems, Sep 2011, Genoa, Italy. ⟨hal-00646520⟩
  • Bruno Courcelle, Irène Durand. Verifying monadic second order graph properties with tree automata. 3rd European Lisp Symposium, May 2010, Lisboa, France. pp.7--21. ⟨hal-00522586⟩
  • Bruno Courcelle, Irène Durand. Tractable constructions of finite automata from monadic second-order formula. Workshop on Logical Approaches to Barriers in Computing and Complexity, Feb 2010, Greifswald, Germany. ⟨hal-00522591⟩
  • Bruno Courcelle. Special tree-width and the verification of monadic second-order graph pr operties. FSTTCS 2010, Dec 2010, Chennai, India. ⟨hal-00646524⟩
  • Bruno Courcelle. On several proofs of the recognizability theorem. CAI 2009 : Conference on Algebraic Informatics, May 2009, Thessaloniki, Greece. pp.78-80. ⟨hal-00401786⟩
  • Bruno Courcelle. Monadic second-order logic for graphs : algorithmic and language theoretical applications. Language Automata Theory and Applications, Apr 2009, Tarragona, Spain. pp.19-22. ⟨hal-00362832⟩
  • Bruno Courcelle. Graph structure and monadic second-order logic : Language theoretical aspects. ICALP 2008, 2008, Reykjavik, Iceland. pp.1-13. ⟨hal-00333842⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté. Efficient First-Order Model-Checking Using Short Labels. Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings, Jun 2008, Changsha, China. pp.159-170, ⟨10.1007/978-3-540-69311-6_18⟩. ⟨hal-00333894⟩
  • Bruno Courcelle, Andrew Twigg. Compact forbidden-set routing. Proceedings STACS 2007, 2007, Aachen, Germany. pp.37-48. ⟨hal-00306341⟩
  • Bruno Courcelle, Mamadou Moustapha Kanté. Graph operations characterizing rank-width and balanced graph expressions. Proccedings of the 33rd International Workshop on Graphs (WG07), Jun 2007, Germany. pp.66--75. ⟨hal-00306343⟩
  • Bruno Courcelle. Monadic second-order queries on graphs : Vertex labelling for efficient evaluation and linear delay enumeration. Algorithms and Complexity in Durham, Third Workshop, Durham, England, 2007, Durham, United Kingdom. pp.3-12. ⟨hal-00334155⟩
  • Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, Andrew Twigg. Forbidden-Set Labeling on Graphs. 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), Portland, Etats-Unis, Aug 2007, Portland, United States. ⟨hal-00369662⟩
  • Bruno Courcelle, Mamadou Moustapha Kanté. Graph Operations Characterizing Rank-Width and Balanced Graph Expressions. Graph-Theoretic Concepts in Computer Science, 2007, Dornburg, Germany. pp.66--75, ⟨10.1007/978-3-540-74839-7_7⟩. ⟨hal-02083560⟩
  • Bruno Courcelle, Christian Delhommé. The modular decomposition of countable graphs : Constructions in monadic second-order logic. Computer Science Logic, 2005, Oxford, United Kingdom. pp.325-338. ⟨hal-00353765⟩

Books1 document

  • Bruno Courcelle, Joost Engelfriet. Graph structure and monadic second-order logic. A language-theoretic approach.. Cambridge University Press, pp.728, 2012, Encyclopedia of Mathematics and its applications, Vol. 138, 978-0-521-89833-1. ⟨hal-00646514⟩

Book sections8 documents

  • Bruno Courcelle. The common structure of the curves having a same Gauss word. A. Adamatzky. Automata, Computation, Universality, Springer, pp.1-37, 2015, Automata, Computation, Universality. ⟨hal-00879514⟩
  • Bruno Courcelle, Irène Durand. Model Checking with Fly-Automata. Ming-Yang Kao Encyclopedia of Algorithms, second edition., Chapitre 20, 2015, 978-3-642-27848-8. ⟨10.1007/978-3-642-27848-8_692-1⟩. ⟨hal-01299432⟩
  • Bruno Courcelle, Irène Durand. Model Checking with Fly-Automata. Encyclopedia of Algorithms, 2015. ⟨hal-01757763⟩
  • Bruno Courcelle. Structuration des graphes et logique. F. Bayart et E. Charpentier. Leçons de Mathématiques d'Aujourd'hui, Volume 4, Cassini, pp.167-194, 2010, Le sel et le fer. ⟨hal-00560955⟩
  • Bruno Courcelle. Program semantics and infinite regular terms. Y. Bertot et al. From Semantics to Computer Science, Essays in Honour of Gilles Kahn, Cambridge University Press, pp.160-163, 2009. ⟨hal-00354861⟩
  • Bruno Courcelle. Quantifier-free definable graph operations preserving recognizability. J. Flum, E. Graedel, T. Wilke. Logic and Automata, History and perspectives, Amsterdam University Press, pp.251-260, 2008, Texts in Logic and Games. ⟨hal-00288471⟩
  • Bruno Courcelle. Décompositions arborescentes. Jean-Claude Fournier. Graphes et applications 2, Lavoisier, pp.195-231, 2007. ⟨hal-00306342⟩
  • Bruno Courcelle, Gilles Kahn, Jean Vuillemin. Algorithms for equivalence and reduction to minimal form for a class of simple recursive equations. Yves Bertot; Gérard Huet; Jean-Jacques Lévy; Gordon Plotkin. From Semantics to Computer Science Essays in Honour of Gilles Kahn, Cambridge University Press 1974, From Semantics to Computer Science Essays in Honour of Gilles Kahn, 9780521518253. ⟨10.1017/CBO9780511770524.009⟩. ⟨hal-01239749⟩