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.

Abstract

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: https://doi.org/10.1007/978-3-662-44522-8_18
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]
Preview
Text - Accepted Version
Download (400kB) | Preview

Export

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

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login