Max-plus automata and size-change abstraction

January 26, 2015

Laure Daviaud (LIF Marseille)

Max-plus automata are weighted automata over the semiring (NU{-infinite}, max, +) that compute some functions from words to NU{-infinite}. More precisely, a max-plus automaton is a non deterministic finite automaton with a weight on each transition. The weight of a given run is the sum of the weights of the transitions along the run and the weight of a word w is the maximum of the weights of the runs labelled by w and going from an initial state to a final state.

In this talk, we will study the asymptotic behaviour of a max-plus automaton and more precisely the maximum length of a word of weight at most n. In particular, I will show that this function is of the form Theta(n^alpha) for a computable rational alpha. I will also explain how this analysis can, in combination with the size-change abstraction, be used for inferring the termination time of an algorithm as a function of the size of its input.

This is a joint work with Thomas Colcombet (LIAFA, Université Paris 7, CNRS) and Florian Zuleger (Vienna University).