Skip to main content

Max-plus automata and tropical identities

Laure Daviaud ( University of Warwick )

In this talk I will discuss the following natural question:

Given a class of computational models C, does there exist two distinct inputs which give the same output for all the models in the class.
I will discuss this question more precisely for weighted automata in general and for max-plus automata in particular. Weighted automata are a quantitative extension of automata which allows to compute values such as costs and probabilities. Max-plus automata are a special case of weighted automata, particularly suitable to model gain optimisation problems.
We will see that in this last case, we end up with particularly intricate (and open) questions, related to finding identities in the semiring of tropical matrices.

Share this: