Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Vol. 51, No. 2, pp. 313336 (2010) 

A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spacesLaurent TruffetEcole des Mines de Nantes, Dpt. AutomatiqueProductique, 4, rue A. Kastler, La Chantrerie, BP 20722 44307 Nantes Cedex 3, France email: Laurent.Truffet@emn.frAbstract: 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 DevelinSturmfels 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. Keywords: tropical algebra, discrete geometry Classification (MSC2000): 06F07, 52C45 Full text of the article (for subscribers):
Electronic version published on: 24 Jun 2010. This page was last modified: 8 Sep 2010.
© 2010 Heldermann Verlag
