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

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

2010-10-18

arxiv.org/abs/1010.3685v1

Journal of Computer and System Sciences, Volume 77, Issue 4, July 2011, Pages 820-833

Computer Science

Data Structures and Algorithms

Scientific paper

10.1016/j.jcss.2010.08.010

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 semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.

Affiliated with

Also associated with

No associations

Rating

The set of realizations of a max-plus linear sequence is semi-polyhedral does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The set of realizations of a max-plus linear sequence is semi-polyhedral, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The set of realizations of a max-plus linear sequence is semi-polyhedral will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306644