Arrow Research search

Author name cluster

Bruno Courcelle

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
2 author rows

Possible papers

32

TCS Journal 2016 Journal Article

Computations by fly-automata beyond monadic second-order logic

  • Bruno Courcelle
  • Irène Durand

The validity of a monadic-second order (MS) expressible property can be checked in linear time on graphs of bounded tree-width or clique-width given with appropriate decompositions. This result is proved by constructing from the MS sentence expressing the property and an integer that bounds the tree-width or clique-width of the input graph, a finite automaton intended to run bottom-up on the algebraic term representing a decomposition of the input graph. As we cannot construct practically the transition tables of these automata because they are huge, we use fly-automata whose states and transitions are computed “on the fly”, only when needed for a particular input. Furthermore, we allow infinite sets of states and we equip automata with output functions. Thus, they can check properties that are not MS expressible and compute values, for example, the number of p-colorings of a graph. We obtain XP and FPT graph algorithms, parameterized by tree-width or clique-width. We show how to construct easily such algorithms by combining predefined automata for basic functions and properties. These combinations reflect the structure of the MS formula that specifies the property to check or the function to compute.

Details DOI

TCS Journal 2008 Journal Article

The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

  • Bruno Courcelle
  • Christian Delhommé

We consider the notion of modular decomposition for countable graphs. The modular decomposition of a graph given with an enumeration of its set of vertices can be defined by formulas of monadic second-order logic. Another result is the definition of a representation of modular decompositions by low degree relational structures. Such relational structures can also be defined in the considered graph by monadic second-order formulas.

Details DOI

CSL Conference 2005 Conference Paper

The Modular Decomposition of Countable Graphs: Constructions in Monadic Second-Order Logic

  • Bruno Courcelle
  • Christian Delhommé

Abstract We show that the modular decomposition of a countable graph can be defined from this graph, given with an enumeration of its set of vertices, by formulas of Monadic Second-Order logic. A second main result is the definition of a representation of modular decompositions by a low degree relational structures, also constructible by Monadic Second-Order formulas.

Details

TCS Journal 2005 Journal Article

The recognizability of sets of graphs is a robust property

  • Bruno Courcelle
  • Pascal Weil

Once the set of finite graphs is equipped with an algebra structure (arising from the definition of operations that generalize the concatenation of words), one can define the notion of a recognizable set of graphs in terms of finite congruences. Applications to the construction of efficient algorithms and to the theory of context-free sets of graphs follow naturally. The class of recognizable sets depends on the signature of graph operations. We consider three signatures related respectively to Hyperedge Replacement (HR) context-free graph grammars, to Vertex Replacement (VR) context-free graph grammars, and to modular decompositions of graphs. We compare the corresponding classes of recognizable sets. We show that they are robust in the sense that many variants of each signature (where in particular operations are defined by quantifier-free formulas, a quite flexible framework) yield the same notions of recognizability. We prove that for graphs without large complete bipartite subgraphs, HR-recognizability and VR-recognizability coincide. The same combinatorial condition equates HR-context-free and VR-context-free sets of graphs. Inasmuch as possible, results are formulated in the more general framework of relational structures.

Details DOI

MFCS Conference 1998 Conference Paper

Facial Circuits of Planar Graphs and Context-Free Languages

  • Bruno Courcelle
  • Denis Lapoire

Abstract It is known that a language is context-free iff it is the set of borders of the trees of recognizable set, where the border of a (labelled) tree is the word consisting of its leaf labels read from left to right. We give a generalization of this result in terms of planar graphs of bounded tree-width. Here the border of a planar graph is the word of edge labels of a path which borders a face for some planar embedding. We prove that a language is context-free iff it is the set of borders of the graphs of a set of (labelled) planar graphs of bounded tree-width which is definable by a formula of monadic second-order logic.

Details

CSL Conference 1995 Conference Paper

Monadic Second-Order Logic and Linear Orderings of Finite Structures

  • Bruno Courcelle

Abstract We consider graphs in which it is possible to specify linear orderings of the sets of vertices, in uniform ways, by MS (i. e. , Monadic Second-order) formulas. We also consider classes of graphs ℂ such that for every L \(\subseteq\) ℂ, L is recognizable iff it is MS-definable. Our results concern in particular dependency graphs of partially commutative words.

Details

MFCS Conference 1989 Invited Paper

Monadic Second-Order Logic and Context-Free Graph-Grammars

  • Bruno Courcelle

Abstract Sets of finite graphs (and hypergraphs) can be defined in different ways: by context-free grammars, by conguences, by logical formulas. We compare these three types of definitions. In particular, we consider certain context-free graph-grammar, the parsing of which can be expressed in monadic second-order logic.

Details

FOCS Conference 1985 Conference Paper

Equivalences and Transformations of Recursive Definitions

  • Bruno Courcelle

This work presents a unified theory of recursive program schemes, context-free grammars, grammars on arbitrary algebraic structures (and actually of recursive definitions of all kind) in terms of regular systems of equations. Several equivalence relations on regular systems (depending on sets of equational axioms) are defined. They are systematically investigated and characterized (in some cases) in terms of system transformations by folding, unfolding and rewriting according to the equational algebraic laws.

Details

FOCS Conference 1980 Conference Paper

On the Expressive Power of Attribute Grammars

  • Bruno Courcelle
  • Paul Franchi-Zannettacci

We examine the possibility of translating an attribute system into a recursive program scheme taking derivation trees as arguments. This is possible if and only if the attribute system is strongly non-circular. The strong non circularity is decidable in polynomial time. Our recursive program schemes allow us to attack the equivalence problem for attribute systems and solve it in a special case properly including the case of purely synthesized systems.

Details

FOCS Conference 1978 Conference Paper

On Recursive Equations Having a Unique Solution

  • Bruno Courcelle

We give conditions on a left-linear Church-Rosser term rewriting system S allowing to define S-normal forms for infinite terms. We obtain a characterization of the S-equivalence of recursive program schemes (i. e. equivalence in all interpretations which validate S considered as a set of axioms). We give sufficient conditions for a recursive program scheme Σ to be S-univocal i. e. to have only one solution up to S-equivalence (considering Σ as a system of equations). For such schemes, we obtain proofs of S-equivalence which do not use any "induction principle". We also consider (SUE)-equivalence where S satisfies the above conditions and E is a set of bilinear equations such that no E-normal form does exist.

Details

FOCS Conference 1976 Conference Paper

Algebraic Families of Interpretations

  • Bruno Courcelle
  • Maurice Nivat

To each family C of interpretations corresponds an equivalence relation among program schemes, namely the equivalence of the program schemes for all interpretation of C. A family C is algebraic if any two programs are C-equivalent iff every partial finite computation of one of them is C-equivalent to some partial finite computation of the other. Our main theorem states that a family C is algebraic iff it is represented with respect to the equivalence of programs by a single interpretation (a C-Herbrand interpretation) which is algebraic (in Scott's sense, roughly speaking). We give examples of algebraic and non algebraic families.

Details