Bruno Courcelle

Orcid: 0000-0002-5545-8970

Affiliations:
  • University of Bordeaux 1, LABRI, France


According to our database1, Bruno Courcelle authored at least 174 papers between 1974 and 2022.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Unfoldings and Coverings of Weighted Graphs.
Fundam. Informaticae, 2022

Order-theoretic Trees: Monadic Second-order Descriptions and Regularity.
Fundam. Informaticae, 2022

Unfoldings and coverings of weighted graphs.
CoRR, 2022

2021
Axiomatization of betweenness in order-theoretic trees.
Log. Methods Comput. Sci., 2021

Induced betweenness in order-theoretic trees.
Discret. Math. Theor. Comput. Sci., 2021

2020
Betweenness of partial orders.
RAIRO Theor. Informatics Appl., 2020

On quasi-planar graphs: Clique-width and logical description.
Discret. Appl. Math., 2020

Grammars and clique-width bounds from split decompositions.
Discret. Appl. Math., 2020

A unified algorithm for colouring graphs of bounded clique-width.
CoRR, 2020

Betweenness in Order-Theoretic Trees.
Proceedings of the Fields of Logic and Computation III, 2020

2018
From tree-decompositions to clique-width terms.
Discret. Appl. Math., 2018

Fly-automata for checking MSO2 graph properties.
Discret. Appl. Math., 2018

2017
Algebraic and logical descriptions of generalized trees.
Log. Methods Comput. Sci., 2017

Several notions of rank-width for countable graphs.
J. Comb. Theory B, 2017

2016
Model Checking with Fly-Automata.
Encyclopedia of Algorithms, 2016

Computations by fly-automata beyond monadic second-order logic.
Theor. Comput. Sci., 2016

2015
Fly-automata for checking monadic second-order properties of graphs of bounded tree-width.
Electron. Notes Discret. Math., 2015

A characterisation of clique-width through nested partitions.
Discret. Appl. Math., 2015

Fly-automata for checking MSO 2 graph properties.
CoRR, 2015

Regularity Equals Monadic Second-Order Definability for Quasi-trees.
Proceedings of the Fields of Logic and Computation II, 2015

2014
Clique-width and edge contraction.
Inf. Process. Lett., 2014

Fly-automata, model-checking and recognizability.
CoRR, 2014

Monadic second-order definable graph orderings.
Log. Methods Comput. Sci., 2014

2013
Infinite Transducers on Terms Denoting Graphs.
Proceedings of ELS 2013 - 6th European Lisp Symposium, Madrid, Spain, June 3-4, 2013., 2013

Model-Checking by Infinite Fly-Automata.
Proceedings of the Algebraic Informatics - 5th International Conference, 2013

2012
Automata for the verification of monadic second-order graph properties.
J. Appl. Log., 2012

Book: Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach.
Bull. EATCS, 2012

On the model-checking of monadic second-order formulas with edge set quantifications.
Discret. Appl. Math., 2012

Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach.
Encyclopedia of mathematics and its applications 138, Cambridge University Press, ISBN: 978-0-521-89833-1, 2012

2011
Compact labelings for efficient first-order model-checking.
J. Comb. Optim., 2011

Fly-Automata, Their Properties and Applications.
Proceedings of the Implementation and Application of Automata, 2011

Automata for Monadic Second-Order Model-Checking.
Proceedings of the Reachability Problems - 5th International Workshop, 2011

2010
Constrained-Path Labellings on Graphs of Bounded Clique-Width.
Theory Comput. Syst., 2010

On the Monadic Second-Order Transduction Hierarchy
Log. Methods Comput. Sci., 2010

Special tree-width and the verification of monadic second-order graph pr operties.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Verifying Monadic Second Order Graph Properties with Tree Automata.
Proceedings of the 3rd European Lisp Symposium (ELS 2010), 2010

2009
Graph operations characterizing rank-width.
Discret. Appl. Math., 2009

Linear delay enumeration and monadic second-order logic.
Discret. Appl. Math., 2009

Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications.
Proceedings of the Language and Automata Theory and Applications, 2009

On Several Proofs of the Recognizability Theorem.
Proceedings of the Algebraic Informatics, Third International Conference, 2009

2008
The modular decomposition of countable graphs. Definition and construction in monadic second-order logic.
Theor. Comput. Sci., 2008

Circle graphs and monadic second-order logic.
J. Appl. Log., 2008

Connectivity check in 3-connected planar graphs with obstacles.
Electron. Notes Discret. Math., 2008

A Multivariate Interlace Polynomial and its Computation for Graphs of Bounded Clique-Width.
Electron. J. Comb., 2008

Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Efficient First-Order Model-Checking Using Short Labels.
Proceedings of the Frontiers in Algorithmics, Second Annual International Workshop, 2008

Quantifier-free definable graph operations preserving recognizability.
Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007
Vertex-minors, monadic second-order logic, and a conjecture by Seese.
J. Comb. Theory B, 2007

A multivariate interlace polynomial
CoRR, 2007

Graph Operations Characterizing Rank-Width and Balanced Graph Expressions.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Compact Forbidden-Set Routing.
Proceedings of the STACS 2007, 2007

2006
The monadic second-order logic of graphs XVI : Canonical graph decompositions.
Log. Methods Comput. Sci., 2006

The monadic second-order logic of graphs XV: On a conjecture by D. Seese.
J. Appl. Log., 2006

Recognizability, hypergraph operations, and logical types.
Inf. Comput., 2006

2005
The recognizability of sets of graphs is a robust property.
Theor. Comput. Sci., 2005

Graph decompositions definable in monadic second-order logic.
Electron. Notes Discret. Math., 2005

The Modular Decomposition of Countable Graphs: Constructions in Monadic Second-Order Logic.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004
Workshop on Logic, Graph Transformations, Finite and Infinite Structures.
Proceedings of the Graph Transformations, Second International Conference, 2004

Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey.
Proceedings of the Developments in Language Theory, 2004

2003
The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications.
Theor. Comput. Sci., 2003

Query efficient implementation of graphs of bounded clique-width.
Discret. Appl. Math., 2003

2002
The evaluation of first-order substitution is monadic second-order compatible.
Theor. Comput. Sci., 2002

Fusion in Relational Structures and the Verification of Monadic Second-Order Properties.
Math. Struct. Comput. Sci., 2002

A Monadic Second-Order Definition of the Structure of Convex Hypergraphs.
Inf. Comput., 2002

Map Genus, Forbidden Maps, and Monadic Second-Order Logic.
Electron. J. Comb., 2002

Workshop on Logic, Graph Transformations and Discrete Structures.
Proceedings of the Graph Transformation, First International Conference, 2002

Semantical Evaluations as Monadic Second-Order Compatible Structure Transformations.
Proceedings of the Foundations of Software Science and Computation Structures, 2002

2001
Graph Operations, Graph Transformations and Monadic Second-Order Logic: a survey.
Proceedings of the GETGRATS Closing Workshop 2001, Bordeaux, France, June 22-23, 2001, 2001

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic.
Discret. Appl. Math., 2001

2000
The monadic second-order logic of graphs XIII: Graph drawings with edge crossings.
Theor. Comput. Sci., 2000

The monadic second-order logic of graphs XII: planar graphs and planar maps.
Theor. Comput. Sci., 2000

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width.
Theory Comput. Syst., 2000

Clique-width of countable graphs: a compactness property.
Electron. Notes Discret. Math., 2000

Upper bounds to the clique width of graphs.
Discret. Appl. Math., 2000

Graph Operations and Monadic Second-Order Logic: A Survey.
Proceedings of the Logic for Programming and Automated Reasoning, 2000

1999
The Monadic Second-Order Logic of Graphs XI: Hierarchical Decompositions of Connected Graphs.
Theor. Comput. Sci., 1999

Hierarchical Graph Decompositions Defined by Grammars and Logical Formulas.
Proceedings of the Rewriting Techniques and Applications, 10th International Conference, 1999

1998
The obstructions of a minor-closed set of graphs defined by a context-free grammar.
Discret. Math., 1998

Monadic Second-Order Logic, Graph Coverings and Unfoldings of Transition Systems.
Ann. Pure Appl. Log., 1998

Facial Circuits of Planar Graphs and Context-Free Languages.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals.
J. Univers. Comput. Sci., 1997

Finite Model Theory, Universal Algebra and Graph Grammars.
Proceedings of the Logical Foundations of Computer Science, 4th International Symposium, 1997

The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic.
Proceedings of the Handbook of Graph Grammars and Computing by Graph Transformations, 1997

1996
Basic Notions of Universal Algebra for Language Theory and Graph Grammars.
Theor. Comput. Sci., 1996

The Monadic Second-Order Logic of Graphs X: Linear Orderings.
Theor. Comput. Sci., 1996

Equivalent Definitions of Recognizability for Sets of Graphs of Bounded Tree-Width.
Math. Struct. Comput. Sci., 1996

On the Expression of Graph Properties in some Fragments of Monadic Second-Order Logic.
Proceedings of the Descriptive Complexity and Finite Models, 1996

1995
Structural Properties of Context-Free Sets of Graphs Generated by Vertex Replacement
Inf. Comput., February, 1995

The Monadic Second-Order Logic of Graphs IX: Machines and their Behaviours.
Theor. Comput. Sci., 1995

A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars.
Math. Syst. Theory, 1995

Mineurs d'arbres avec racines.
RAIRO Theor. Informatics Appl., 1995

Logic and graphs.
Proceedings of the Joint COMPUGRAPH/SEMAGRAPH Workshop on Graph Rewriting and Computation, 1995

The Monadic Second-Order Logic of Graphs VIII: Orientations.
Ann. Pure Appl. Log., 1995

1994
Monadic Second-Order Definable Graph Transductions: A Survey.
Theor. Comput. Sci., 1994

Recognizable Sets of Graphs: Equivalent Definitions and Closure Properties.
Math. Struct. Comput. Sci., 1994

Coverings and Minors: Application to Local Computations in Graphs.
Eur. J. Comb., 1994

The Monadic Second order Logic of Graphs VI: on Several Representations of Graphs By Relational Structures
Discret. Appl. Math., 1994

The Obstructions of a Minor-Closed Set of Graphs Defined by Hyperedge Replacement can be Constructed.
Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

The Definition in Monadic Second-Order Logic of Modular Decompositions of Ordered Graphs.
Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Monadic Second-Order Logic and Linear Orderings of Finite Structures.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993
Monadic Second-Order Evaluations on Tree-Decomposable Graphs.
Theor. Comput. Sci., 1993

Handle-Rewriting Hypergraph Grammars.
J. Comput. Syst. Sci., 1993

An Algebraic Theory of Graph Reduction.
J. ACM, 1993

Graphs and Monadic Second-Order Logic: Some Open Problems.
Bull. EATCS, 1993

Monadic Second-Order Logic and Hypergraph Orientation
Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

Context-Free Graph Grammars: Separating Vertex Replacement from Hyperedge Replacement.
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

Recognizable Sets of Graphs of Bounded Tree-Width.
Proceedings of the Graph Transformations in Computer Science, International Workshop, 1993

Graph Rewriting: A Bibliographical Guide.
Proceedings of the Term Rewriting, 1993

1992
The Monadic Second-Order Logic of Graphs VII: Graphs as Relational Structures.
Theor. Comput. Sci., 1992

The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues.
RAIRO Theor. Informatics Appl., 1992

Monadic Second-Order Graph Transductions.
Proceedings of the CAAP '92, 1992

Recognizable sets of unrooted trees.
Proceedings of the Tree Automata and Languages., 1992

1991
The Monadic Second-Order Logic of Graphs V: On Closing the Gap Between Definability and Recognizability.
Theor. Comput. Sci., 1991

Recursive Queries and Context-free Graph Grammars.
Theor. Comput. Sci., 1991

A Geometrical View of the Determinization and Minimization of Finite-State Automata.
Math. Syst. Theory, 1991

On Constructing Obstruction Sets of Words.
Bull. EATCS, 1991

Graph grammars, monadic second-order logic and the theory of graph minors.
Proceedings of the Graph Structure Theory, 1991

1990
The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs
Inf. Comput., March, 1990

The Monadic Second-Order Logic of Graphs IV: Definability Properties of Equational Graphs.
Ann. Pure Appl. Log., 1990

On the Expression of Monadic Second-Order Graph Properties Without Quantifications Over Sets of Edges (Extended Abstract)
Proceedings of the Fifth Annual Symposium on Logic in Computer Science (LICS '90), 1990

Context-free Handle-rewriting Hypergraph Grammars.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

Graphs as Relational Structures: An Algebraic an Logical Approach.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

The Logical Exprssion of Graph Properties (Abstract).
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1990

Recursive Applicative Program Schemes.
Proceedings of the Handbook of Theoretical Computer Science, 1990

Graph Rewriting: An Algebraic and Logic Approach.
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
The Monadic Second-Order Logic of Graphs, II: Infinite Graphs of Bounded Width.
Math. Syst. Theory, 1989

Monadic Second-Order Logic and Context-Free Graph-Grammars.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

The Definability of Equational Graphs in Monadic Second-Order Logic.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988
Proofs of Partial Correctness for Attribute Grammars with Applications to Recursive Procedures and Logic Programming
Inf. Comput., July, 1988

The Monadic Second-Order Logic of Graphs: Definable Sets of Finite Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1988

1987
An Axiomatic Definition of Context-Free Rewriting and its Application to NLC Graph Grammars.
Theor. Comput. Sci., 1987

Graph Expressions and Graph Rewritings.
Math. Syst. Theory, 1987

Decidable Subcases of The Equivalence Problem for Recursive Program Schemes.
RAIRO Theor. Informatics Appl., 1987

1986
Equivalences and Transformations of Regular Systems-Applications to Recursive Program Schemes and Grammars.
Theor. Comput. Sci., 1986

On context-free sets of graphs and their monadic second-order theory.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

A representation of graphs by algebraic expressions and its use for graph rewriting systems.
Proceedings of the Graph-Grammars and Their Application to Computer Science, 1986

An Algebraic Formalism for Graphs.
Proceedings of the CAAP '86, 1986

1985
Proofs of partial correctness for iterative and recursive computations.
Proceedings of the Logic Colloquium '85, Orsay, France, 1985

Equivalences and Transformations of Recursive Definitions
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
The Solutions of Two Star-Height Problems for Regular Trees.
Theor. Comput. Sci., 1984

Définitions Récursives Par Cas.
RAIRO Theor. Informatics Appl., 1984

Some Negative Results Concerning DPDA's.
Inf. Process. Lett., 1984

The solution of two star height problems for regular trees.
Proceedings of the Automata on Infinite Words, 1984

1983
Fundamental Properties of Infinite Trees.
Theor. Comput. Sci., 1983

An Axiomatic Approach to the Korenjak-Hopcroft Algorithms.
Math. Syst. Theory, 1983

A Class of Program Schemes Based on Tree Rewriting Systems.
Proceedings of the CAAP'83, 1983

Attribute Grammars: Definitions, Analysis of Dependencies, Proof Methods.
Proceedings of the Method and tools for compiler construction, 1983

1982
On the Equivalence Problem for Attribute Systems
Inf. Control., March, 1982

Attribute Grammars and Recursive Program Schemes II.
Theor. Comput. Sci., 1982

Attribute Grammars and Recursive Program Schemes I.
Theor. Comput. Sci., 1982

1981
The Rational Index: A Complexity Measure for Languages.
SIAM J. Comput., 1981

The Simultaneous Accessibility of Two Configurations of Two Equivalent DPDA's.
Inf. Process. Lett., 1981

Attribute Grammars: Theory and Applications.
Proceedings of the Formalization of Programming Concepts, 1981

1980
Completions of ordered magmas.
Fundam. Informaticae, 1980

On the Expressive Power of Attribute Grammars
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
Infinite Trees in Normal Form and Recursive Equations Having a Unique Solution.
Math. Syst. Theory, 1979

Arbes infinis et systèmes d'équations.
RAIRO Theor. Informatics Appl., 1979

1978
A Representation of Trees by Languages II.
Theor. Comput. Sci., 1978

A Representation of Trees by Languages I.
Theor. Comput. Sci., 1978

On Some Classes of Interpretations.
J. Comput. Syst. Sci., 1978

Frontiers of Infinite Trees.
RAIRO Theor. Informatics Appl., 1978

The Algebraic Semantics of Recursive Program Schemes.
Proceedings of the Mathematical Foundations of Computer Science 1978, 1978

On Recursive Equations Having a Unique Solution
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
On Jump-Deterministic Pushdown Automata.
Math. Syst. Theory, 1977

On a description of tree-languages by languages.
Proceedings of the Theoretical Computer Science, 1977

On the Definition of Classes of Interpretations.
Proceedings of the Automata, 1977

1976
Completeness Results for the Equivalence of Recursive Schemas.
J. Comput. Syst. Sci., 1976

Program Equivalence and Canonical Forms in Stable Discrete Interpretations.
Proceedings of the Third International Colloquium on Automata, 1976

Algebraic Families of Interpretations
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1974
Une forme canonique pour les grammaires simples déterministes.
RAIRO Theor. Informatics Appl., 1974

Semantics and Axiomatics of a Simple Recursive Language
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

Complétude d'un système formel pour prouver l'équivalence de certains schémas récursifs monadiques.
Proceedings of the Programming Symposium, 1974

Algorithmes d'equivalence et de reduction a des expressions minimales dans une classe d'equations recursives simples.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

Recursive Schemes, Algebraic Trees and Deterministic Languages
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974


  Loading...