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

Vincent Blondel 1 Stéphane Gaubert 2, 3 Natacha Portier 4, 5
1 INMA - Pôle en ingénierie mathématique
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
3 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 DCS - Department of Computer Science [University of Toronto]
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.
Keywords : max-plus algebra minimal realization discrete event systems semi-polyhedral set formal series semiring
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00507757
Contributor : Natacha Portier <>
Submitted on : Monday, October 18, 2010 - 8:57:39 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:30 PM
Long-term archiving on : Wednesday, January 19, 2011 - 2:55:41 AM

Files

RR-BGP.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA | LIP | X | PARISTECH | X-CMAP | ENS-LYON | CMAP | UNIV-LYON1 | X-DEP-MATHA

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

656

Files downloads

539

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD