The Complexity of Stratification Computation

This paper investigates the complexity of stratification computation for semialgebraic sets. An upper bound for the computation of canonical stratifications is given for a wide class of stratifying conditions called here admissible. For such conditions, the stratifying process is at most doubly exponential in the depth of the stratification. Usual conditions of regularity like Whitney conditions (a) and (b) or Bekka condition (C) are admissible. A useful criterion and tools are given in order to prove easily other admissibilities. Received February 15, 1995, and in revised form January 29, 1997 and May 6, 1997.