Minimal (max,+) realization of convex sequences

Stéphane Gaubert; Peter Butkovič; Raymond Cuninghame-Green

doi:10.1137/S036301299528534X

Minimal (max,+) realization of convex sequences

Stéphane Gaubert
, Peter Butkovič
, Raymond Cuninghame-Green

University of Birmingham

Research output: Contribution to journal › Article › peer-review

45 Citations (Scopus)

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.

Original language	English
Pages (from-to)	137-147
Number of pages	11
Journal	SIAM Journal on Control and Optimization
Volume	36
Issue number	1
DOIs	https://doi.org/10.1137/S036301299528534X
Publication status	Published - 1 Jan 1998

Keywords

Discrete-event systems
Max plus algebra
Minimal realization
Rational sequences

Access to Document

10.1137/S036301299528534X

Cite this

@article{28c0dc630b404c0dbc26f2004561cd3b,

title = "Minimal (max,+) realization of convex sequences",

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 = "Discrete-event systems, Max plus algebra, Minimal realization, Rational sequences",

author = "St{\'e}phane Gaubert and Peter Butkovi{\v c} and Raymond Cuninghame-Green",

year = "1998",

month = jan,

day = "1",

doi = "10.1137/S036301299528534X",

language = "English",

volume = "36",

pages = "137--147",

journal = "SIAM Journal on Control and Optimization",

issn = "0363-0129",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Minimal (max,+) realization of convex sequences

AU - Gaubert, Stéphane

AU - Butkovič, Peter

AU - Cuninghame-Green, Raymond

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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.

AB - 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.

KW - Discrete-event systems

KW - Max plus algebra

KW - Minimal realization

KW - Rational sequences

U2 - 10.1137/S036301299528534X

DO - 10.1137/S036301299528534X

M3 - Article

AN - SCOPUS:0031674279

SN - 0363-0129

VL - 36

SP - 137

EP - 147

JO - SIAM Journal on Control and Optimization

JF - SIAM Journal on Control and Optimization

IS - 1

ER -

Minimal (max,+) realization of convex sequences

Abstract

Keywords

Access to Document

Fingerprint

Cite this