DOC

characterizations

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

    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 :

    http://www.labri.fr/perso/courcell/ActSci.html

    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.

     2

     Summary

    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

     3

1. Introduction : An overview chart

    Graph "Context-free"

    operations sets of graphs

Fixed parameter tractable

    algorithms Language theory

     for graphs

     Recognizable

     sets of graphs

    ndnd

    Monadic 2 order Monadic 2order

    logic transductions

     4

    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

    transductions

     5

    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)

     6

Another picture :

     Value ( MS Transduction)

    REC(Terms) EQ

     MS Transductions

     Coding

     (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

     7

    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.

     8

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.

     9

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).

     10

Report this document

For any questions or suggestions please email
cust-service@docsford.com