Abstract: This presentation considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been successfully implemented. Our result also fits in a wider scheme whose objective is to improve the techniques for converting automata-based representation of constraints to formulas.

Axel Legay was born in 1980, Verviers, Belgium. In 2002 he obtained his diploma in computer science from the University of Liè and became a member of Pierre Wolper's team. In 2003, he obtained a master in computer sciences and entered in the Ph.D. program of the University of Liège. Legay will defend his Thesis in December 2007 and then become a Postdoc at Carnegie Mellon. Axel Legay's main research interests include verification methods for reactive and concurrent programs based on an automata-theory approach. Appointments: dcm@cs.cmu.edu