|
  |
Seminars & Workshops
The Equational, Rational Path Ordering
| Speaker: | Jean-Pierre Jouannaud , École Polytechnique |
|---|---|
| When: | 2016-03-04 11:00 |
| Place: | Rm 309, Bldg 302, SNU |
Abstract
The Equational, Rational Path Ordering is a well-founded ordering on certain graph expressions whose definition is inspired by that of the Recursive Path Ordering, and which enjoys all prop- erties that have made RPO popular, in particular well-foundedness and monotonicity. Being equational, the ordering is also compatible with any given congruence on expressions satisfying certain axiomatic properties. Associativity and commutativity is an example of such a congru- ence. Last, but not least, the ordering decreases when sharing decreases, a crucial property if one wants to avoid dandling pointers when rewriting expressions with sharing, and increases, as expected, when unfolding rational branches.
We are indeed interested in a generalization of algebraic expressions called operadic, in which elements are graphs whose each vertex is labelled by a function symbol, the arity of which governs the number of vertices it relates to in the graph. These graphs are seen here as terms with sharing and back-arrows. Further, some function symbols may be associative-commutative, implying that the corresponding vertex can be related to an unbounded number of other vertices having a different label. Operadic expressions occur in algebraic topology, and in various areas of computer science, notably concurrency and type theory. Rewriting operadic expressions is very much like rewriting algebraic expressions. ERPO provides with a first building block for computing with operadic expressions.
Short bio
Jean-Pierre Jouannaud graduated from École Polytechnique de Paris and obtained his doctorate from University Paris 6 in 1978. He was then a professor successively at the universities of Nancy, then Paris-Sud, and finally at École Polytechnique, in France, as well as an invited professor at a number of places, including Stanford Research Institute and Stanford University in US (2 years), the Polytechnicum University of Catalugna in Spain (1 year), Keio University in Tokyo (6 months), Japan, National Taiwan University in Taipei (4 months), Taiwan, and Tsinghua University in Beijing, China (5 years). He is now Professor emeritus at University Paris-Sud and École Polytechnique in France.