1. The set of realizations of a max-plus linear sequence is semi-polyhedral
- Author
-
Natacha Portier, Stéphane Gaubert, Vincent D. Blondel, Pôle en ingénierie mathématique (INMA), Université Catholique de Louvain = Catholic University of Louvain (UCL), Max-plus algebras and mathematics of decision (MAXPLUS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [University of Toronto] (DCS), University of Toronto, 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., European Project: 236197,EC:FP7:PEOPLE,FP7-PEOPLE-IOF-2008,PACCAP(2009), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
- Subjects
FOS: Computer and information sciences ,0209 industrial biotechnology ,Computer Networks and Communications ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,semiring ,01 natural sciences ,Theoretical Computer Science ,Semiring ,Set (abstract data type) ,Combinatorics ,020901 industrial engineering & automation ,formal series ,Dimension (vector space) ,[INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering ,Computer Science - Data Structures and Algorithms ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Data Structures and Algorithms (cs.DS) ,Commutative property ,Mathematics ,Discrete mathematics ,Sequence ,Applied Mathematics ,Minimal realization ,max-plus algebra ,minimal realization ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Idempotence ,semi-polyhedral set ,discrete event systems ,Realization (systems) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; 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.
- Published
- 2011
- Full Text
- View/download PDF