Mercredi 25 Septembre


Retour à la vue des calendrier
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.