Lambda-Upsilon-Omega: An Assistant Algorithms Analyzer

Philippe Flajolet B. Salvy P. Zimmermann 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : Lambda-Upsilon-Omega, ΛΥΩ, is a system designed to perform automatic analysis of well-defined classes of algorithms operating over "decomposable" data structures. It consists of an 'Algebraic Analyzer' System that compiles algorithms specifications into generating functions of average costs, and an 'Analytic Analyzer' System that extracts asymptotic informations on coefficients of generating functions. The algebraic part relies on recent methodologies in combinatorial analysis based on systematic correspondences between structural type definitions and counting generating functions. The analytic part makes use of partly classical and partly new correspondences between singularities of analytic functions and the growth of their Taylor coefficients. The current version ΛΥΩ0 of ΛΥΩ implements as basic data types, term trees as encountered in symbolic algebra systems. The analytic analyzer can treat large classes of functions with explicit expressions. In this way, ΛΥΩ0 can generate in the current stage about a dozen non-trivial average case analyses of algorithms like: formal differentiation, some algebraic simplification and matching algorithms. Its analytic analyzer can determine asymptotic expansions for large classes of generating functions arising in the analysis of algorithms. The outline of a design for a full system is also discussed here. The long term goal is to include a fairly rich set of data structuring mechanisms including some general recursive type definitions, and have the analytic analyzer treat wide classes of functional equations as may be encountered in combinatorial analysis and the analysis of algorithms.
Type de document :
Communication dans un congrès
Teo Mora. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 1989, Rome, Italy. 357, pp.201-212, 1989, Lecture Notes in Computer Science. 〈10.1007/3-540-51083-4_60〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00917731
Contributeur : Paul Zimmermann <>
Soumis le : jeudi 12 décembre 2013 - 12:42:22
Dernière modification le : vendredi 25 mai 2018 - 12:02:02

Lien texte intégral

Identifiants

Collections

Citation

Philippe Flajolet, B. Salvy, P. Zimmermann. Lambda-Upsilon-Omega: An Assistant Algorithms Analyzer. Teo Mora. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 1989, Rome, Italy. 357, pp.201-212, 1989, Lecture Notes in Computer Science. 〈10.1007/3-540-51083-4_60〉. 〈hal-00917731〉

Partager

Métriques

Consultations de la notice

103