Rice University
Department of Computer Science
presents

Alexandru Mateescu

University of Turku and University of Bucharest

Parallel composition: Words and graphs

Abstract

We introduce and investigate new principles to define parallel composition of words and parallel composition of graphs. Parallel composition of words leads to new shuffle-like operations defined as a syntactical property or as a semantical property. The operations are extended to graphs and labeled graphs.

A geometrical interpretation of the parallel composition is considered in order to investigate various properties of these operations. The approach provides the possibility to introduce in a natural way, and to study, important concepts like determinism, order (priority), communication, bisimulation, fairness, re-entrance, composability, etc.

Some new and interesting problems of research are presented in connection with fields like concurrency, formal languages and automata, algebra, and combinatorics. As a consequence, there are useful applications to concurrency where parallel composition of processes is a fundamental operation.

The talk is self contained, no previous knowledge is assumed.

Friday, May 16 @ 2 p.m. in Duncan Hall 1064
Reception to follow in Duncan Hall 1044