MINIMAL (MAX,+) REALIZATION OF CONVEX SEQUENCES

Authors
GAUBERT S BUTKOVIC P CUNINGHAMEGREEN R
Citation
S. Gaubert et al., MINIMAL (MAX,+) REALIZATION OF CONVEX SEQUENCES, SIAM journal on control and optimization, 36(1), 1998, pp. 137-147
Citations number
33
Categorie Soggetti
Mathematics,"Robotics & Automatic Control",Mathematics,"Robotics & Automatic Control
Journal title
SIAM journal on control and optimization → ACNP
ISSN journal
03630129
Volume
36
Issue
1
Year of publication
1998
Pages
137 - 147
Database
ISI
SICI code
0363-0129(1998)36:1<137:M(ROCS>2.0.ZU;2-D
Abstract
We show that the minimal dimension of a linear realization over the (m ax,+) semiring of a convex sequence is equal to the minimal size of a decomposition of the sequence as a supremum of discrete affine maps. T he minimal-dimensional realization of any convex realizable sequence c an thus be found in linear time. The result is based on a bound in ter ms of minors of the Hankel matrix.