CGL Meeting Agenda

Wednesday, September 3rd, 1997

Location:
DC 1304
Time:
13:30
Chair:
Michael McCool

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:
CS Barbeque
Coffee hour next week:
???

3. Next meeting

Date:
September 10th, 1997
Location:
DC 1304
Time:
13:30
Chair:
Peter Harwood
Technical presentation:
Michael McCool

4. Forthcoming

Chairs:

  1. Celine Latulipe (9/17)
  2. Marryat Ma (9/24)
  3. Leo Magalhaes (10/1)
  4. Mike Hammond (10/8)

Tech Presenters:

  1. None; John Ousterhout talking (9/17)
  2. Peter Harwood (9/24)
  3. Celine Latulipe (10/1)
  4. Marryat Ma (10/8)

5. Technical Presentation

Presenter:
Patrick Gilhuly
Title:
The SGI Video Library
Abstract:
How the real-time SGI media library works and what it means to you.

6. General Discussion Items

7. Action List

8. Director's Meeting

9. Seminars


        ICR SHORT COURSES:
        
        

        Master's Thesis Presentation - Wednesday, September 3, 1997

        Russell  Mok,  Graduate Student, Department of Computer
        Science,   University   of   Waterloo,  will  speak  on
        ``Abnormal event handling mechanisms''.

        ROOM:          Davis Centre Room DC1304
        TIME:          2:30 - 3:30 p.m.

        Master's Presentation - Friday, September 5, 1997

         Vlado  Keselj, Graduate Student, Department of Computer
         Science,   University   of   Waterloo,  will  speak  on
         ``Multi-Agent    Systems   for   Internet   Information
         Retrieval Using Natural Language Processing''.
                
        TIME:       10:00 - 11:00 a.m.
        ROOM:          Davis Centre Room DC2305 (AI Lab)

THEORY SEMINAR -Monday,  September  8,  1997  

Zoltan Esik, Joszef Attila University, Szeged, Hungary,
will speak on ``Shuffling Languages and Posets: Are Two
Models of Concurrency Equivalent?''
TIME:                3:30-4:30 p.m.
ROOM:                DC 1304

ABSTRACT

How can one do formal computations with languages?

For  the collection of the regular operations of union,
concatenation,  iteration  and  the  constants 0 and 1,
denoting  the empty set and the set containing only the
empty  word,  this  question has been studied since the
1960's  (by  Redko,  Salomaa,  Conway, Krob, Kozen, and
others).    The   equational  properties  of  languages
equipped  with  these  operations and constants are the
same as those of the binary relations equipped with the
operations  of  union,  relative product and reflexive-
transitive closure, where 0 is interpreted as the empty
relation and 1 as the identity relation.

In  this  talk, we enlarge the collection of operations
by  the operations of shuffle and iterated shuffle.  We
consider  formal  equations between expressions (terms)
composed  of variables ranging over languages using the
above   operations  and constants.  Such an equation is
valid  if  its  two sides evaluate to the same language
under  all  interpretations  of the variables. We study
questions  concerning  the  validity  of equations, the
decidability     and     complexity     of    validity,
axiomatizability, etc. In the specific answers given to
these questions, we will relate equations that hold for
languages  to equations that hold for (series-parallel)
posets.

In  the  interleaving or language model of concurrency,
also known as the trace model, the parallel composition
of  two  processes  is  given by shuffle and sequential
composition  by concatenation.  In 1986, Pratt proposed
labeled  posets,  called  pomsets,  and sets of labeled
posets, as another model of concurrency.  In his ``true
concurrency''  model,  parallel composition is given by
disjoint  union  and  sequential  composition by serial
product  of  labeled posets. The series-parallel posets
mentioned  above  are  those  generated  from the empty
poset   and  the  singletons  by  serial  and  parallel
product.  The results of the talk seem to indicate that
the  pomset  model  of concurrency is equivalent to the
language model.

10. Lab Cleanup (until 14:30 or 5 minutes)