Minimal (max,+) Realization of Convex Sequences. St\'ephane Gaubert, Peter Butkovi\v{c}, Raymond Cuninghame-Green. Final version 1996. To appear in SIAM J. on Control and Opt.

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.