The set of realizations of a max-plus linear sequence is semi-polyhedral - Archive ouverte HAL Access content directly
Journal Articles Journal of Computer and System Sciences Year : 2011

The set of realizations of a max-plus linear sequence is semi-polyhedral

(1) , (2, 3) , (4, 5)
1
2
3
4
5

Abstract

We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.
Fichier principal
Vignette du fichier
RR-BGP.pdf (317.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ensl-00507757 , version 1 (30-07-2010)
ensl-00507757 , version 2 (18-10-2010)

Identifiers

Cite

Vincent Blondel, Stéphane Gaubert, Natacha Portier. The set of realizations of a max-plus linear sequence is semi-polyhedral. Journal of Computer and System Sciences, 2011, 77 (4), pp.820-833. ⟨10.1016/j.jcss.2010.08.010⟩. ⟨ensl-00507757v2⟩
348 View
457 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More