********************************************************************* * Ecole Normale Supe'rieure * * * * Se'minaire * * SEMANTIQUE ET INTERPRETATION ABSTRAITE * * P. Cousot * * * * Vendredi, 14h00--15h30 * * Salle R, etage -1 * * DI ENS 45 rue d'Ulm 75005 Paris * ********************************************************************* *** Vendredi 2 fevrier 2001 **** 14h00 ****************************** Rela^che *** Vendredi 9 fevrier 2001 **** 14h00 ****************************** Helmut SEIDL (Universität Trier) Analyzing Asymptotic Complexities Re'sume' : We consider the problem of automatically deriving tight asymptotic complexity bounds for a solver algorithm. The solver algorithm determines a set of relations forming the minimal model of a first-order formula from some fragment of predicate logic. Clearly, the runtime of the solver crucially depends on the ``sparseness'' of the computed relations. Therefore, we present an asymptotic sparseness calculus together with an asymptotic sparseness analysis. The technical problem here stems from the observation that classical least fixpoint iteration fails on asymptotic complexity expressions: $O(1) + O(1) = O(1)$ but $O(1) + \cdots + O(1)$ may return any value. (joint work with Flemming Nielson) *** Vendredi 16 fevrier 2001 **** 14h00 ***************************** Rela^che (vacances d'hiver) *** Vendredi 23 fevrier 2001 **** 14h00 ***************************** Rela^che ********************************************************************* Pour recevoir l'annonce par courrier electronique: cousot@di.ens.fr WWW: http://www.di.ens.fr/~cousot/annonceseminaire.shtml *********************************************************************