City Research Online

Size-Change Abstraction and Max-Plus Automata

Colcombet, T., Daviaud, L. and Zuleger, F. (2014). Size-Change Abstraction and Max-Plus Automata. In: Csuhaj-Varju, E., Dietzfelbinger, M. and Esik, Z. (Eds.), Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, 8634. (pp. 208-219). Berlin: Springer. ISBN 9783662445211

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 Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/21300
[img]
Preview
Text - Accepted Version
Download (400kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login