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

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.
Mots-clés : max-plus
Complete list of metadatas

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00507757
Contributor : Natacha Portier <>
Submitted on : Friday, July 30, 2010 - 8:49:05 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:30 PM
Long-term archiving on : Thursday, November 4, 2010 - 10:54:19 AM

Files

BGP.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00507757, version 1

Collections

Citation

Natacha Portier, Vincent Blondel, Stéphane Gaubert. The set of realizations of a max-plus linear sequence is semi-polyhedral. 2010. ⟨ensl-00507757v1⟩

Share

Metrics

Record views

19

Files downloads

23