The set of realizations of a max-plus linear sequence is semi-polyhedral - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2010

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

Résumé

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

Fichier principal
Vignette du fichier
BGP.pdf (318.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : ensl-00507757 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More