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. 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 Science & Technology > Computer Science |
|
Text
- Accepted Version
Download (400kB) | Preview |
Export
Downloads
Downloads per month over past year
Metadata
Metadata