City Research Online

Size-Change Abstraction and Max-Plus Automata

Colcombet, T., Daviaud, L. & Zuleger, F. (2014). Size-Change Abstraction and Max-Plus Automata. In: Csuhaj-Varju, E., Dietzfelbinger, M. & Esik, Z. (Eds.), Mathematical Foundations of Computer Science 2014. MFCS 2014.


Max-plus automata (over ℕ ∪ − ∞) are finite devices that map input words to non-negative integers or − ∞. In this paper we present (a) an algorithm allowing to compute the asymptotic behaviour of max-plus automata, and (b) an application of this technique to the evaluation of the computational time complexity of programs.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: This is a post-peer-review, pre-copyedit version of an article published in Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8634. The final authenticated version is available online at:
Publisher Keywords: Weighted Matrice, Asymptotic Order, Computational Time Complexity, Weighted Automaton, Boolean Semiring
Departments: School of Science & Technology > Computer Science
[thumbnail of main_max_plus.pdf]
Text - Accepted Version
Download (400kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login