Beitr\ EMIS ELibM Electronic Journals Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 51, No. 2, pp. 313-336 (2010)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

 		 

A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces

Laurent Truffet

Ecole 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.

© 2010 Heldermann Verlag
© 2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition