Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!ylfink
From: ylfink@water.UUCP
Newsgroups: ont.events,uw.talks
Subject: Tree Monoids.
Message-ID: <1157@water.waterloo.edu>
Date: Wed, 7-Oct-87 13:45:41 EDT
Article-I.D.: water.1157
Posted: Wed Oct  7 13:45:41 1987
Date-Received: Sat, 10-Oct-87 01:58:02 EDT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 57
Keywords: Dr. M. Nivat, Thurs., Oct. 8/87, 3:30PM, MC 6091A.
Xref: utgpu ont.events:724 junk:5996


DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    - Thursday, October 8, 1987

Dr.  Maurice Nivat, visiting the Department of Computer
Science, will speak on ``Tree Monoids''.

TIME:                3:30 PM

ROOM:              MC 6091A

ABSTRACT

                 #
If  t member of A   is a binary tree whose nodes are labeled by
elements  in  A,  the  set delta (t) of border nodes of t is
defined as the set of nodes which are not in the domain
of t but are sons of nodes in the domain of t.  The set
                                     #
of  pairs  (t, f) where t member of A  and f member of delta (t) 
is a monoid when equipped with the composition law
             (t, f) + (s, g) = (t + sf, fg)
where t + sf is the union of t and the translation of s
by f (one just places the root of s in f).  To a subset
      (#)
L of A    there is thus attached

-   the canonically defined syntactic congruence =   ,
                                                 - L

-                         (#)
    the syntactic monoid A    / =   .
                                - L

The results are:

-   L  is  recognizable  by  a  finite  ascending  tree
                                            (#)
    automaton  iff =   has finite index iff A    / =   is
                   - L                             - L


                         - 2 -

    finite,

-   there  exists  a  minimal  ascending  deterministic
    finite tree automata recognizing L whose transition
    monoid  is precisely the syntactic monoid of L when
    this monoid is finite.

                    October 7, 1987