| Identifiant de l'article : |
 |
ensl-00507757, version 2 |
|
|
| Identifiant arXiv : |
|
arXiv:1010.3685 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
The set of realizations of a max-plus linear sequence is semi-polyhedral |
|
|
| Auteur(s) : |
|
Vincent Blondel1, Stéphane Gaubert2, 3, Natacha Portier4, 5 |
|
|
| Laboratoire : |
|
| 1 : |
INMA - Pôle en ingénierie mathématique |
|
| 2 : |
INRIA Saclay - Ile de France - MAXPLUS |
|
| 3 : |
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique |
|
| 4 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 5 : |
Department of Computer Science |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| 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. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
max-plus algebra – minimal realization – discrete event systems – semi-polyhedral set – formal series – semiring |
|
|
| Référence interne : |
|
Research Report RRLIP 2010-33 |
|
|
| Contrat, financement : |
|
This work was partly supported by a grant Tournesol (Programme de coopération scientifique entre la France et la communauté Française de Belgique) and by the European Community Framework IV program through the research network ALAPEDES (``The Algebraic Approach to Performance Evaluation of Discrete Event Systems'') and by European Community under contract PIOF-GA-2009-236197 of the 7th PCRD. |
|
|
Récupérer au format
