By Grace Rivera,2014-09-15 10:48
8 views 0

    Monadic second-order logic

    and recognizability

    Bruno Courcelle

    Université Bordeaux 1, LaBRI, and

    Institut Universitaire de France

References : Book in progress,

    Articles with J. Makowsky, U. Rotics, P. Weil, S. Oum, A. Blumensath ; See :

    History : Confluence of 4 independent research directions, now intimately related :

    1. Polynomial algorithms for NP-complete and other hard problems on particular

    classes of graphs, and especially hierarchically structured ones : series-parallel

    graphs, cographs, partial k-trees, graphs or hypergraphs of tree-width < k, graphs of

    clique-width < k.

    2. Excluded minors and related notions of forbidden configurations (matroid

    minors, ? vertex-minors ?).

    3. Decidability of Monadic Second-Order logic on classes of finite graphs, and on

    infinite graphs.

    4. Extension to graphs and hypergraphs of the main concepts of Formal

    Language Theory : grammars, recognizability, transductions, decidability questions.



    1. Introduction

    Extension of Formal Language Theory notions 2. Recognizability, an algebraic notion. 3. Context-free sets defined by equation systems. 4. The graph algebras VR and HR.

    5. Monadic second-order logic defines inductive properties and functions

    6. Monadic second-order transductions.

    7. Preservation of recognizability by inverse monadic second-order transductions.

    8. Preservation of recognizability by quantifier-free definable operations.

    Open questions


1. Introduction : An overview chart

    Graph "Context-free"

    operations sets of graphs

Fixed parameter tractable

    algorithms Language theory

     for graphs


     sets of graphs


    Monadic 2 order Monadic 2order

    logic transductions


    Key concepts of FLT and their extensions

    Languages Graphs

    Algebraic structure : ?,;? // Algebras based on graph operations :

    quantifier-free definable operations monoid (X*,,?) *

    Algebras : HR, VR Context-free languages : Equational sets of the

    algebras HR,VR Equational subsets of (X*,,?) *

    Regular languages : Recognizable sets

    of the algebras Finite automata ?

    HR, VR

    Finite congruences ? defined by congruences Regular expressions ?

    ?;;;Monadic Second-order ?;

    definable sets of words or terms Monadic Second-order definable sets of graphs Rational and other types of Monadic Second-order transductions



    Relationships between algebraic and logical notions

    for sets of graphs (and hypergraphs)

    Algebraic Algebraic Logical Closure

    notions characterizations characterizations properties

     union, ?;Rec

    equation systems MS-trans(Trees) homo EQ

    Val(REC(Terms)) MS-trans

    Boolean opns

    -1congruences REC homoMS-def ?;REC

    -1 MS-trans

Signatures for graph algebras :

    HR : graphs and hypergraphs with “sources”

    VR : graphs with vertex labels, “ports”


    VR : VR with (QF) quantifier-free operations (ex. edge complement)


Another picture :

     Value ( MS Transduction)

    REC(Terms) EQ

     MS Transductions


     (MS Transductions) MS Transduction

     Binary trees

    Equational sets = MS-Trans(Binary Trees)

    Context-free languages = images of the Dyck language (which encodes trees)

    under rational transductions

    Since MS transductions are closed under composition, the class of equational sets

    is closed under MS transductions


    2. Recognizable sets : algebraic definition

    F : a finite set of operations with (fixed) arity.

    M = < M, (f)? > : an F-algebra. Mf F

    Definition : L ? M is (F-)recognizable if it is a union of equivalence classes for a finite congruence ?;;; on M (finite means that M / ?;; is finite).

    -1Equivalently, L = h(D) for a homomorphism h : M ? A, where A is a finite F-

    algebra, D ? A. (On terms : Finite deterministic automata).

    REC(M) is the set of recognizable subsets of M, with respect to the algebra M.

    Closure properties : REC(M) contains M and ?, and is closed under union, intersection and difference.


The many-sorted case with infinitely many sorts

S : the countable set of sorts.

    F : an S-signature : each f in F has a type ss …s ? s, with s, s ? S 12ki

    M = < (M), (f) > F-algebra, M?;M=?, if s ;;t ss ? SMf ? Fs t

    where f : MX MX X M?; M Ms1 s2 sk s

    Definition : L ? M is (F-) recognizable if it is a union of equivalence classes for a s

    congruence ? on M such that equivalent elements are of the same sort and there are finitely many classes of each sort.


3. Equational (context-free) sets

    Equation systems = Context-Free (Graph) Grammars in an algebraic setting

    In the case of words, the set of context-free rules

    S ? a S T ; S ? b ; T ? c T T T ; T ? a

    is equivalent to the system of two set equations:

     S = a S T ? { b }

     T = c T T T ? { a }

    where S is the language generated by S (idem for T and T).


Report this document

For any questions or suggestions please email