Derived terms without derivation

The topic of this talk is the transformation of rational 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 rational (or 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. It is particularly well-suited to the case of weighted rational expressions and it broadens the scope of the method to (weighted) expressions over non free monoids.

Joint work with Sylvain Lombardy. 

Date and Venue

Start Date
Room FC6029 (CS Bldg., FCUP) and Online
End Date


Jacques Sakarovitch

Speaker's Institution

IRIF, CNRS-U. Paris Cité & LTCI, Télécom Paris



Semigroups, Automata and Languages