ylfink@water.UUCP (10/07/87)
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