I am a researcher in the Maxplus team joint to INRIA and Centre de Mathématiques Appliquéees (CMAP) of École Polytechnique.

I am interested in the combinatorial and algorithmic aspects of convexity in tropical algebra, and their applications to software verification.

Publications:

  • Xavier Allamigeon and Bruno Blanchet. Reconstruction of Attacks against Cryptographic Protocols. In 18th IEEE Computer Security Foundations Workshop (CSFW-18), pages 140-154, Aix-en-Provence, France, June 2005. IEEE Computer Society. [ bib | pdf ]
  • Xavier Allamigeon, Wenceslas Godard, and Charles Hymans. Static Analysis of String Manipulations in Critical Embedded C Programs. In Kwangkeun Yi, editor, Static Analysis, 13th International Symposium (SAS'06), volume 4134 of Lecture Notes in Computer Science, pages 35-51, Seoul, Korea, August 2006. Springer Verlag. [ bib | pdf ]
  • Xavier Allamigeon and Charles Hymans. Analyse Statique par Interprétation Abstraite : Application à la Détection de Dépassement de Tampon. In Eric Filiol, editor, 5ème Symposium sur la Sécurité des Technologies de l'Information et des Communications (SSTIC'07), pages 347-384, Rennes, France, June 2007. ESAT. [ bib | pdf ]
  • Xavier Allamigeon and Charles Hymans. Static Analysis by Abstract Interpretation: Application to the Detection of Heap Overflows. Journal in Computer Virology, 4(1):5-23, 2008. [ bib ]
  • Xavier Allamigeon. Non-disjunctive Numerical Domain for Array Predicate Abstraction. In Sophia Drossopoulou, editor, Programming Languages and Systems, Proceedings of the 17th European Symposium on Programming (ESOP'08), volume 4960 of Lecture Notes in Computer Science, pages 163-177, Budapest, Hungary, April 2008. Springer Verlag. [ bib | pdf ]
  • Xavier Allamigeon, Stéphane Gaubert, and Eric Goubault. Inferring Min and Max Invariants Using Max-plus Polyhedra. In María Alpuente and Germán Vidal, editors, Proceedings of the 15th International Static Analysis Symposium (SAS'08), volume 5079 of Lecture Notes in Computer Science, pages 189-204, Valencia, Spain, July 2008. Springer Verlag. [ bib | pdf ]
  • Xavier Allamigeon, Stéphane Gaubert, and Eric Goubault. The Tropical Double Description Method. In J.-Y. Marion and Th. Schwentick, editors, Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47-58, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. [ bib | http ]
  • Xavier Allamigeon, Stéphane Gaubert, and Ricardo D. Katz. The number of extreme points of tropical polyhedra. Journal of Combinatorial Theory, Series A, 118(1):162-189, 2011. [ bib | http ]
  • Xavier Allamigeon, Stéphane Gaubert, and Ricardo D. Katz. Tropical polar cones, hypergraph transversals, and mean payoff games. Linear Algebra and its Applications, 435(7):1549-1574, 2011. [ bib | http ]

Preprints:

  • Xavier Allamigeon, Stéphane Gaubert, and Eric Goubault. Computing the vertices of tropical polyhedra using directed hypergraphs. Submitted, December 2011. [ bib | http ]
  • Xavier Allamigeon. Strongly connected components of directed hypergraphs. Submitted, December 2011. [ bib | http ]
  • Xavier Allamigeon, Uli Fahrenberg, Stéphane Gaubert, Ricardo D. Katz, and Axel Legay. Strict Inequalities in the Tropics. Submitted, April 2012. [ bib ]

PhD thesis:

Xavier Allamigeon. Static analysis of memory manipulations by abstract interpretation - Algorithmics of tropical polyhedra, and application to abstract interpretation. PhD thesis, École Polytechnique, Palaiseau, France, November 2009. [ bib | pdf ]. More details here.

Won the Gilles Kahn prize 2010 for best dissertation in Computer Science.

Software:

I am the author of TPLib (Tropical Polyhedra Library), which is an OCaml library allowing to manipulate tropical polyhedra, and to use them as a numerical abstract domain. Now interfaced with polymake.

How to contact me:

CMAP, Ecole Polytechnique
91128 Palaiseau cedex, France
Phone: +33 1 69 33 46 32
Email: