Computer Science seminar
Date: Wednesday, 23rd March 2022
Time: 2 PM to 3:15 PM
Venue: Seminar Hall (this talk will be held in hybrid mode)
Derived terms without derivation
Jacques Sakarovitch
IRIF, CNRS - U. Paris & LTCI, Télécom Paris, IPP, France.
23-03-22

---

Abstract

The topic of this talk is the transformation of regular expressions into finite automata, a much laboured subject indeed.

The starting point is the derived term automaton (aka partial derivative, or Antimirov, automaton) of a regular expression, a modification of Brzozowski derivative automaton. By taking a shifted perspective, I shall present a construction of this automaton based on a sole induction on the depth of the expression and that does not make reference to any operation of derivation of the expression. The whys and wherefores of the construction will led me to sketch a survey of the whole subject.

The construction is particularly well-suited to the case of weighted expressions and it broadens the scope of the method to (weighted) expressions over non free monoids (eg to expressions over direct products of free monoids that yield transducers).

Joint work with Sylvain Lombardy (LaBRI, U. Bordeaux)