|
|
Mercredi 25 Septembre
Heure: |
14:00 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Brzozowski and Antimirov reordering derivatives |
Description: |
Tarmo Uustalu The Brzozowski and Antimirov derivatives are effective operations on regular expressions that calculate the (semantic) derivatives of a regular language. They yield constructions of finite deterministic and nondeterministic automata.
In this talk, I show how these operations on regular expressions admit natural generalizations for trace closures of regular languages, which are languages obtained from a regular language by allowing some pairs of letters to commute.
The automata from the Brzozowski and Antimirov reordering derivatives are generally not finite. But if the regular expression is star-connected or, more generally, if its language has uniform rank, they are.
This is joint work with Hendrik Maarand.
I will also give a short introduction to what we do in my groups in Tallinn and Reykjavik. |
|
|