The set of realizations of a max-plus linear sequence is semi-polyhedral

Vincent Blondel; Stéphane Gaubert; Natacha Portier

doi:10.1016/j.jcss.2010.08.010

The set of realizations of a max-plus linear sequence is semi-polyhedral

Vincent Blondel
, Stéphane Gaubert
, Natacha Portier

Large Graphs and Networks
University of Louvain
University of Lyon
University of Toronto

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

1 Citation (Scopus)

Abstract

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 finite union of polyhedral sets.

Original language	English
Pages (from-to)	820-833
Number of pages	14
Journal	Journal of Computer and System Sciences
Volume	77
Issue number	4
DOIs	https://doi.org/10.1016/j.jcss.2010.08.010
Publication status	Published - 1 Jan 2011

Keywords

Discrete event systems
Formal series
Max-plus algebra
Minimal realization
Semi-polyhedral set
Semiring

Access to Document

10.1016/j.jcss.2010.08.010

Cite this

@article{ab06e29c9a78428da22233eef096475c,

title = "The set of realizations of a max-plus linear sequence is semi-polyhedral",

abstract = "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 finite union of polyhedral sets.",

keywords = "Discrete event systems, Formal series, Max-plus algebra, Minimal realization, Semi-polyhedral set, Semiring",

author = "Vincent Blondel and St{\'e}phane Gaubert and Natacha Portier",

year = "2011",

month = jan,

day = "1",

doi = "10.1016/j.jcss.2010.08.010",

language = "English",

volume = "77",

pages = "820--833",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - The set of realizations of a max-plus linear sequence is semi-polyhedral

AU - Blondel, Vincent

AU - Gaubert, Stéphane

AU - Portier, Natacha

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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 finite union of polyhedral sets.

AB - 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 finite union of polyhedral sets.

KW - Discrete event systems

KW - Formal series

KW - Max-plus algebra

KW - Minimal realization

KW - Semi-polyhedral set

KW - Semiring

U2 - 10.1016/j.jcss.2010.08.010

DO - 10.1016/j.jcss.2010.08.010

M3 - Article

AN - SCOPUS:79952536081

SN - 0022-0000

VL - 77

SP - 820

EP - 833

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 4

ER -

The set of realizations of a max-plus linear sequence is semi-polyhedral

Abstract

Keywords

Access to Document

Fingerprint

Cite this