Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 51, No. 2, pp. 313-336 (2010)
A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces
Laurent TruffetEcole des Mines de Nantes, Dpt. Automatique-Productique, 4, rue A. Kastler, La Chantrerie, BP 20722 44307 Nantes Cedex 3, France e-mail: Laurent.Truffet@emn.fr
Abstract: 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.
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.