×

A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces. (English) Zbl 1342.52026

Summary: In this paper we study the generators of idempotent polyhedral cones which appear of main importance in many fields of applications such as control of discrete event systems, verification of concurrent systems, analysis of Petri nets. We give an explicit formula for the set of generators. This formula makes clearly appear the role of the data used to describe the idempotent polyhedral cone. This formula is based on the Develin-Sturmfels cellular decomposition. From this formula we provide an algorithm which could be easily partially parallelizable. From this formula we also give a bound on the number of generators and the expression of the necessary and sufficient condition under which the set of generators is reduced to the null space. We illustrate our results on an example of transportation network.

MSC:

52C45 Combinatorial complexity of geometric structures
15B48 Positive matrices and their generalizations; cones of matrices
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52B11 \(n\)-dimensional polytopes
06F99 Ordered structures
PDFBibTeX XMLCite
Full Text: EMIS