ylfink@water.UUCP (11/10/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
FORMAL LANGUAGE THEORY SEMINAR
- Thursday, November 12, 1987
Dr. Jacques Sakarovitch, of the Laboratoire
Informatique Theorique et Programmation, Paris, France,
will speak on ``On Regular Trace Languages (And Other
Stories)''.
TIME: 3:30 PM
ROOM: MC 6082
ABSTRACT
The starting point of the work that will be reported in
the seminar is the characterization of commutation
relations with the property that the corresponding
regular trace languages are closed under
complementation or are unambiguous. This will be
established as a consequence of a property of free
products (of monoids). This property, in turn, will be
proved by means of a generalization of finite automata
(that has been more or less folklore up to now) and
that gives new insights on several classical results,
as Chomsky normal form for context-free grammars.