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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2011, 77 (4), pp.820-833. 〈10.1016/j.jcss.2010.08.010〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00507757
Contributeur : Natacha Portier <>
Soumis le : lundi 18 octobre 2010 - 20:57:39
Dernière modification le : mercredi 14 novembre 2018 - 15:20:11
Document(s) archivé(s) le : mercredi 19 janvier 2011 - 02:55:41

Fichiers

RR-BGP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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, Elsevier, 2011, 77 (4), pp.820-833. 〈10.1016/j.jcss.2010.08.010〉. 〈ensl-00507757v2〉

Partager

Métriques

Consultations de la notice

615

Téléchargements de fichiers

441