Mostrar el registro sencillo del ítem
dc.contributor.author
Allamigeon, Xavier
dc.contributor.author
Fahrenberg, Uli
dc.contributor.author
Gaubert, Stéphane
dc.contributor.author
Katz, Ricardo David
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Legay, Axel
dc.date.available
2016-03-16T15:35:15Z
dc.date.issued
2014-08
dc.identifier.citation
Allamigeon, Xavier; Fahrenberg, Uli; Gaubert, Stéphane; Katz, Ricardo David; Legay, Axel; Tropical Fourier-Motzkin Elimination, with an Application to Real-Time Verification; World Scientific; International Journal of Algebra and Computation; 24; 5; 8-2014; 569-607
dc.identifier.issn
0218-1967
dc.identifier.uri
http://hdl.handle.net/11336/4812
dc.description.abstract
We introduce a generalization of tropical polyhedra able to express both strict and non-strict inequalities. Such inequalities are handled by means of a semiring of germs (encoding infinitesimal perturbations). We develop a tropical analogue of Fourier-Motzkin elimination from which we derive geometrical properties of these polyhedra. In particular, we show that they coincide with the tropically convex union of (non-necessarily closed) cells that are convex both classically and tropically. We also prove that the redundant inequalities produced when performing successive elimination steps can be dynamically deleted by reduction to mean payoff game problems. As a complement, we provide a coarser (polynomial time) deletion procedure which is enough to arrive at a simply exponential bound for the total execution time. These algorithms are illustrated by an application to real-time systems (reachability analysis of timed automata).
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
World Scientific
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Tropical Polyhedra
dc.subject
Strict Inequalities
dc.subject
Fourier-Motzkin Elimination
dc.subject
Mean Payoff Games
dc.subject
Real-Time Verification
dc.subject
Timed Automata
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Tropical Fourier-Motzkin Elimination, with an Application to Real-Time Verification
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2016-03-30 10:35:44.97925-03
dc.journal.volume
24
dc.journal.number
5
dc.journal.pagination
569-607
dc.journal.pais
Singapur
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Toh Tuck
dc.description.fil
Fil: Allamigeon, Xavier. École Polytechnique. French National Institute for Computer Science and Applied Mathematics; Francia. Ecole Polytechnique. Centre de Mathematiques Appliquees; Francia
dc.description.fil
Fil: Fahrenberg, Uli. Institut National de Recherche en Informatique et en Automatique; Francia
dc.description.fil
Fil: Gaubert, Stéphane. Ecole Polytechnique. Centre de Mathematiques Appliquees; Francia. École Polytechnique. French National Institute for Computer Science and Applied Mathematics; Francia
dc.description.fil
Fil: Katz, Ricardo David. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Rosario. Centro Internacional Franco Argentino de Ciencias de la Información y Sistemas; Argentina
dc.description.fil
Fil: Legay, Axel. Institut National de Recherche en Informatique et en Automatique; Francia
dc.journal.title
International Journal of Algebra and Computation
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.worldscientific.com/doi/abs/10.1142/S0218196714500258
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://arxiv.org/abs/1308.2122
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://hal.inria.fr/hal-01087367
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/10.1142/S0218196714500258
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1142/S0218196714500258
Archivos asociados