Minimal (max,+) Realization of Convex Sequences
Authors:
- Stéphane GaubertSGStéphane Gaubert
- Peter ButkovicPBPeter Butkovic
- Raymond Cuninghame-GreenRCRaymond Cuninghame-Green
- 1 January 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 36 (1) , 137-147
Abstract
We show that the minimal dimension of a linear realization over the (max,+) semiring of a convex sequence is equal to the minimal size of a decomposition of the sequence as a supremum of discrete affine maps. The minimal-dimensional realization of any convex realizable sequence can thus be found in linear time. The result is based on a bound in terms of minors of the Hankel matrix.Keywords
This publication has 11 references indexed in Scilit:
- Discrete-event dynamic systems: The strictly convex caseAnnals of Operations Research, 1995
- Permanents, max algebra and optimal assignmentLinear Algebra and its Applications, 1995
- The characteristic equation and minimal state space realization of SISO systems in the max algebra1994
- Minimax algebra and applicationsFuzzy Sets and Systems, 1991
- The minimal realization of discrete-event systems *IFAC Proceedings Volumes, 1991
- Algebraic realization of discrete dynamic systemsIFAC Proceedings Volumes, 1991
- Rational Series and Their Languages1988
- On the Characteristic Equation and Minimal Realizations for Discrete-Event Dynamic Systems1986
- Inversion of matrices over a commutative semiringJournal of Algebra, 1984
- Linear Algebra in Dioids: A Survey of Recent Results1984