Weighted Automata and Epsilon-Transitions

Weighted automata were designed by M.-P. Schützenberger to recognize languages beyond regular languages. Nowadays, the functions realized by these devices are studied; they represent fuzzy computations, probabilities, cost functions, execution times, etc. depending on the nature of the weights. Epsilon-transitions are a common feature of finite automata and their extension to weighted automata seems to be straightforward. Yet, they can lead to an infinite amount of accepting runs for a given input, and, therefore, the study of the behaviour of such machines is not trivial. Finally, we focus on the problem of the extension of the well-known Thompson automaton in the weighted case that leads to some unexpected outcomes.

Joint work with Jacques Sakarovitch.

Date and Venue

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


Sylvain Lombardy

Speaker's Institution

Labri, U. Bordeaux



Semigroups, Automata and Languages