# Bruno Courcelle

#56,189

Most Influential Person Now

French mathematician and computer scientist

## Bruno Courcelle's AcademicInfluence.com Rankings

Bruno Courcellecomputer-science Degrees

Computer Science

#3042

World Rank

#3190

Historical Rank

Theoretical Computer Science

#72

World Rank

#72

Historical Rank

Bruno Courcellemathematics Degrees

Mathematics

#3905

World Rank

#5649

Historical Rank

Graph Theory

#47

World Rank

#54

Historical Rank

Measure Theory

#1034

World Rank

#1331

Historical Rank

## Download Badge

Computer Science Mathematics

## Bruno Courcelle's Degrees

- PhD Mathematics Université Paris Cité

## Why Is Bruno Courcelle Influential?

(Suggest an Edit or Addition)According to Wikipedia, Bruno Courcelle is a French mathematician and computer scientist, best known for Courcelle's theorem in graph theory. Life Courcelle earned his Ph.D. in 1976 from the French Institute for Research in Computer Science and Automation, then called IRIA, under the supervision of Maurice Nivat. He then joined the Laboratoire Bordelais de Recherche en Informatique at the University of Bordeaux 1, where he remained for the rest of his career. He has been a senior member of the Institut Universitaire de France since 2007.

## Bruno Courcelle's Published Works

### Published Works

- The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs (1990) (1394)
- Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width (2000) (682)
- Graph Rewriting: An Algebraic and Logic Approach (1991) (670)
- Upper bounds to the clique width of graphs (2000) (597)
- Fundamental Properties of Infinite Trees (1983) (523)
- Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach (2012) (474)
- The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic (1997) (368)
- Handle-Rewriting Hypergraph Grammars (1993) (336)
- Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width (1998) (336)
- The Monadic Second-order Logic of Graphs VI: On Several Representations of Graphs by Relational Structures (1995) (332)
- Monadic Second-Order Evaluations on Tree-Decomposable Graphs (1991) (265)
- Monadic Second-Order Definable Graph Transductions: A Survey (1994) (232)
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (2001) (213)
- An algebraic theory of graph reduction (1990) (204)
- The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues (1992) (185)
- An Axiomatic Definition of Context-Free Rewriting and its Application to NLC Graph Grammars (1987) (152)
- The Monadic Second-Order Logic of Graphs V: On Closing the Gap Between Definability and Recognizability (1991) (140)
- The Monadic Second order Logic of Graphs VI: on Several Representations of Graphs By Relational Structures (1994) (139)
- Attribute Grammars and Recursive Program Schemes I (1982) (125)
- Attribute Grammars and Recursive Program Schemes II (1982) (125)
- The Monadic Second-Order Logic of Graphs X: Linear Orderings (1996) (119)
- Equivalences and Transformations of Regular Systems-Applications to Recursive Program Schemes and Grammars (1986) (109)
- Vertex-minors, monadic second-order logic, and a conjecture by Seese (2007) (109)
- Recursive Applicative Program Schemes (1991) (107)
- The Monadic Second-Order Logic of Graphs IV: Definability Properties of Equational Graphs (1990) (106)
- Graph expressions and graph rewritings (1987) (99)
- Algebraic families of interpretations (1976) (86)
- The Monadic Second-Order Logic of Graphs VII: Graphs as Relational Structures (1992) (79)
- A Representation of Trees by Languages II (1978) (79)
- Monadic Second-Order Logic, Graph Coverings and Unfoldings of Transition Systems (1998) (76)
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width (1988) (76)
- Linear delay enumeration and monadic second-order logic (2009) (76)
- On Recognizable Sets and Tree Automata (1989) (75)
- A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars (1995) (72)
- Graph Structure and Monadic Second-Order Logic: Overview (2012) (70)
- The monadic second-order logic of graphs XVI : Canonical graph decompositions (2005) (67)
- The Monadic Second-Order Logic of Graphs VIII: Orientations (1995) (66)
- The Algebraic Semantics of Recursive Program Schemes (1978) (64)
- The Monadic Second-Order Logic of Graphs IX: Machines and their Behaviours (1995) (60)
- A Representation of Trees by Languages I (1978) (56)
- Frontiers of Infinite Trees (1978) (56)
- The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications (2003) (54)
- Query efficient implementation of graphs of bounded clique-width (2003) (51)
- On Constructing Obstruction Sets of Words (1991) (49)
- Basic Notions of Universal Algebra for Language Theory and Graph Grammars (1996) (49)
- Structural Properties of Context-Free Sets of Graphs Generated by Vertex Replacement (1995) (44)
- Compact Forbidden-Set Routing (2007) (44)
- The monadic second-order logic of graphs XV: On a conjecture by D. Seese (2006) (38)
- On the model-checking of monadic second-order formulas with edge set quantifications (2012) (38)
- Context-free Handle-rewriting Hypergraph Grammars (1990) (37)
- Coverings and Minors: Application to Local Computations in Graphs (1994) (35)
- On context-free sets of graphs and their monadic second-order theory (1986) (35)
- Graph grammars, monadic second-order logic and the theory of graph minors (1991) (35)
- Graph Structure and Monadic Second-Order Logic: Frontmatter (2012) (34)
- Proofs of Partial Correctness for Attribute Grammars with Applications to Recursive Procedures and Logic Programming (1988) (34)
- A Multivariate Interlace Polynomial and its Computation for Graphs of Bounded Clique-Width (2008) (33)
- Circle graphs and monadic second-order logic (2008) (33)
- Automata for the verification of monadic second-order graph properties (2012) (33)
- On the Expression of Graph Properties in some Fragments of Monadic Second-Order Logic (1996) (32)
- The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs (1988) (32)
- Clique-width of countable graphs: a compactness property (2000) (31)
- Recursive Queries and Context-free Graph Grammars (1991) (31)
- Verifying Monadic Second Order Graph Properties with Tree Automata (2010) (29)
- The monadic second-order logic of graphs XII: planar graphs and planar maps (2000) (28)
- On the Monadic Second-Order Transduction Hierarchy (2010) (28)
- A representation of graphs by algebraic expressions and its use for graph rewriting systems (1986) (28)
- Recognizable sets of graphs: equivalent definitions and closure properties (1994) (27)
- The recognizability of sets of graphs is a robust property (2005) (26)
- Monadic Second-Order Logic, Graphs and Unfoldings of Transition Systems (1995) (25)
- The modular decomposition of countable graphs. Definition and construction in monadic second-order logic (2008) (24)
- Completeness Results for the Equivalence of Recursive Schemas (1976) (24)
- The monadic second-order logic of graphs XIII: Graph drawings with edge crossings (2000) (23)
- Graph operations characterizing rank-width (2009) (22)
- On Some Classes of Interpretations (1978) (22)
- Special tree-width and the verification of monadic second-order graph pr operties (2010) (22)
- The Monadic Second-Order Logic of Graphs XI: Hierarchical Decompositions of Connected Graphs (1999) (21)
- Attribute Grammars: Definitions, Analysis of Dependencies, Proof Methods (1984) (21)
- The Rational Index: A Complexity Measure for Languages (1981) (21)
- Recognizability, hypergraph operations, and logical types (2006) (20)
- A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (1997) (19)
- Monadic Second-Order Graph Transductions (1992) (19)
- Constrained-Path Labellings on Graphs of Bounded Clique-Width (2010) (18)
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions (2007) (17)
- Recursive Schemes, Algebraic Trees and Deterministic Languages (1974) (17)
- Computations by fly-automata beyond monadic second-order logic (2013) (16)
- On the Equivalence Problem for Attribute Systems (1982) (16)
- On jump-deterministic pushdown automata (1977) (16)
- Completions of ordered magmas (1980) (15)
- The evaluation of first-order substitution is monadic second-order compatible (2002) (15)
- Equivalent definitions of recognizability for sets of graphs of bounded tree-width (1996) (15)
- A characterisation of clique-width through nested partitions (2015) (15)
- Semantics and axiomatics of a simple recursive language. (1974) (14)
- Graphs as Relational Structures: An Algebraic an Logical Approach (1990) (14)
- Clique-width and edge contraction (2013) (13)
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects (2008) (13)
- Graph Structure and Monadic Second-Order Logic: Monadic second-order logic (2012) (13)
- From tree-decompositions to clique-width terms (2017) (13)
- A geometrical view of the determinization and minimization of finite-state automata (1991) (13)
- The Solutions of Two Star-Height Problems for Regular Trees (1984) (12)
- The solution of two star height problems for regular trees (1984) (10)
- Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey (2004) (10)
- Program Equivalence and Canonical Forms in Stable Discrete Interpretations (1976) (9)
- Infinite trees in normal form and recursive equations having a unique solution (1979) (9)
- Linear Time Solvable Optimization Problems on Certain Structured Graph Families (1997) (9)
- The Definability of Equational Graphs in Monadic Second-Order Logic (1989) (9)
- Attribute Grammars: Theory and Applications (1981) (8)
- Several notions of rank-width for countable graphs (2017) (8)
- Fly-Automata, Their Properties and Applications (2011) (8)
- Connectivity check in 3-connected planar graphs with obstacles (2008) (8)
- A multivariate interlace polynomial (2007) (8)
- Graph Operations and Monadic Second-Order Logic: A Survey (2000) (8)
- Monadic second-order definable graph orderings (2013) (8)
- Graph Operations, Graph Transformations and Monadic Second-Order Logic: a survey (2002) (8)
- on recursive equations having a unique solution (1978) (7)
- Graph Structure and Monadic Second-Order Logic: Algorithmic applications (2012) (7)
- Recognizable sets of unrooted trees (1992) (7)
- Regularity Equals Monadic Second-Order Definability for Quasi-trees (2015) (6)
- Algebraic and logical descriptions of generalized trees (2016) (6)
- The Modular Decomposition of Countable Graphs: Constructions in Monadic Second-Order Logic (2005) (6)
- An Algebraic Formalism for Graphs (1986) (5)
- Map Genus, Forbidden Maps, and Monadic Second-Order Logic (2002) (5)
- Graph Rewriting: A Bibliographical Guide (1993) (5)
- Optimal Labeling for Connectivity Checking in Planar Networks with Obstacles (2009) (5)
- An axiomatic approach to the Korenjak-Hopcroft algorithms (1981) (5)
- A Monadic Second-Order Definition of the Structure of Convex Hypergraphs (2002) (5)
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width (2015) (5)
- Model-Checking by Infinite Fly-Automata (2013) (5)
- Clique-width and tree-width of sparse graphs (2015) (5)
- Axiomatization of betweenness in order-theoretic trees (2020) (4)
- On the Definition of Classes of Interpretations (1977) (4)
- Context-Free Graph Grammars: Separating Vertex Replacement from Hyperedge Replacement (1993) (4)
- Efficient First-Order Model-Checking Using Short Labels (2008) (4)
- Infinite Transducers on Terms Denoting Graphs (2013) (4)
- Betweenness in Order-Theoretic Trees (2020) (3)
- Recognizable Sets of Graphs of Bounded Tree-Width (1993) (3)
- On the expression of monadic second-order graph properties without quantifications over sets of edges (1990) (3)
- Fly-automata, model-checking and recognizability (2014) (3)
- Compact labelings for efficient first-order model-checking (2008) (3)
- The Simultaneous Accessibility of Two Configurations of Two Equivalent DPDA's (1981) (3)
- Forbidden-Set Labeling on Graphs (2007) (3)
- Fly-automata for checking MSO 2 graph properties (2015) (3)
- The obstructions of a minor-closed set of graphs defined by a context-free grammar (1998) (3)
- On the expressive power of attribute grammars (1980) (3)
- The Logical Exprssion of Graph Properties (Abstract) (1990) (2)
- Graph decompositions definable in monadic second-order logic (2005) (2)
- A Class of Program Schemes Based on Tree Rewriting Systems (1983) (2)
- Monadic second-order logic and hypergraph orientation (1993) (2)
- On quasi-planar graphs: Clique-width and logical description (2017) (2)
- Monadic Second-Order Logic and Linear Orderings of Finite Structures (1994) (2)
- Finite Model Theory, Universal Algebra and Graph Grammars (1997) (2)
- Betweenness of partial orders (2020) (2)
- Decidable Subcases of The Equivalence Problem for Recursive Program Schemes (1987) (2)
- Facial Circuits of Planar Graphs and Context-Free Languages (1998) (2)
- Proofs of partial correctness for iterative and recursive computations (1985) (2)
- Some Negative Results Concerning DPDA's (1984) (1)
- Equivalences and transformations of recursive definitions (1985) (1)
- The Definition in Monadic Second-Order Logic of Modular Decompositions of Ordered Graphs (1994) (1)
- On defining linear orders by automata (2019) (1)
- Graph algebras and widths of graphs (2012) (1)
- The Obstructions of a Minor-Closed Set of Graphs Defined by Hyperedge Replacement can be Constructed (1994) (1)
- A unified algorithm for colouring graphs of bounded clique-width (2020) (1)
- Monadic Second-Order Logic and Context-Free Graph-Grammars (1989) (1)
- Automata for Monadic Second-Order Model-Checking (2011) (1)
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications (2009) (1)
- The Common Structure of the Curves Having a Same Gauss Word (2015) (1)
- The atomic decomposition of strongly connected graphs (2013) (1)
- Equational Theories and Equivalences of Programs (1984) (1)
- Unfoldings and coverings of weighted graphs (2022) (1)
- Semantical Evaluations as Monadic Second-Order Compatible Structure Transformations (2002) (0)
- Graph Structure and Monadic Second-Order Logic, chapters 7-10 (2009) (0)
- Forbidden-Set Labeling on Graphs B (2007) (0)
- Ninth Colloquium on Trees in Algebra and Programming : 5-7 March 1984, Bordeaux, France : [proceedings] (1984) (0)
- Hjorth, G., Kechris, AS and Louveau, A., Bore1 equivalence (1998) (0)
- Acknowledgement to referees (2005) (0)
- Acknowledgement to referees (2004) (0)
- Monadic second-order transductions of terms and words (2009) (0)
- Workshop on Logic, Graph Transformations and Discrete Structures (2002) (0)
- Grammars and clique-width bounds from split decompositions (2020) (0)
- Hierarchical Graph Decompositions Defined by Grammars and Logical Formulas (1999) (0)
- European School on Graph Transformation Pullback Rewriting Algebraic Approaches the Logical Expression of Graph Properties and Graph Transformations (2007) (0)
- Conclusion and open problems (2012) (0)
- Algebraic and Regular Trees (1985) (0)
- Graph Structure and Monadic Second-Order Logic: Equational and recognizable sets of graphs (2012) (0)
- Order-theoretic trees: monadic second-order descriptions and regularity (2021) (0)
- ЯUSSIAN WORKSHOP ON COMPLEXITY AND MODEL THEORY 9–11 JUNE 2019 ABSTRACTS (2019) (0)
- From Semantics to Computer Science: Algorithms for equivalence and reduction to minimal form for a class of simple recursive equations (1974) (0)
- Graphs and Monadic Second-Order Logic: Some Open Problems (1993) (0)
- Workshop on Logic, Graph Transformations, Finite and Infinite Structures (2004) (0)
- A note on the minimalization of tree-automata (1988) (0)
- Graph Structure and Monadic Second-Order Logic: Transductions of terms and words (2012) (0)
- Proc. of the conference on Ninth colloquium on trees in algebra and programming (1984) (0)
- Logic and graphs (1995) (0)
- Program semantics and infinite regular terms (2009) (0)
- Quantifier-free definable graph operations preserving recognizability (2008) (0)
- Graph Structure and Monadic Second-Order Logic: Monadic second-order transductions (2012) (0)
- Graph Structure and Monadic Second-Order Logic: References (2012) (0)
- Graph-Transformations in Computer Science (Dagstuhl Seminar 9301) (2021) (0)
- On a description of tree-languages by languages (1977) (0)
- Mémoire d’habilitation à diriger des recherches Studying Graphs: Structure via Rank-Width, and Listing of Minimal Dominating Sets (2016) (0)
- Model Checking with Fly-Automata (2016) (0)
- Fundamental Study The monadic second-order logic of graphs XII: planar graphs and planar maps 1 (2000) (0)
- Induced betweenness in order-theoretic trees (2021) (0)
- Graph Structure and Monadic Second-Order Logic: Equational and recognizable sets in many-sorted algebras (2012) (0)
- On Several Proofs of the Recognizability Theorem (2009) (0)

This paper list is powered by the following services:

## Other Resources About Bruno Courcelle

## What Schools Are Affiliated With Bruno Courcelle?

Bruno Courcelle is affiliated with the following schools: