Version française
Home     About     Download     Resources     Contact us    
Browse thread
Automatic complexity analysis of OCaml programs
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jacques Carette <carette@m...>
Subject: Re: [Caml-list] Automatic complexity analysis of OCaml programs
Also the work of the people-next-door to the Ocaml developers, namely the ALGO project.  See their web page at 
http://algo.inria.fr/.

In particular the work of Philippe Flajolet, Bruno Salvy and Marni Mishna (spanning many years) on "automatic 
complexity analysis", *especially* the asymptotic average-case analyses are quite impressive.  They have been doing 
this since 1989, but 'hiding' in the combinatorics and algorithms communities, and somehow their work seems to have 
(unfortunately) escaped the attention of the programming language community.

Jacques

Frédéric Gava <frederic.gava@wanadoo.fr> wrote:
> Hi,
> 
> See the works of
> - Kevin Hammond about inference cost equation.
> - Bernd Grobauer about cost recurrence for DML programs,
> - Whei-Nagan and Siau-Chaeng Khoo about sized types,
> - Daniel Le metayer, ACE an automatic complexity evaluator,
> - Brian Reistad and David K. Gifford about satic dependent costs for
> estimating program excution time
>  - Mads Rosendahl: "automatic complexity analysis"  (cost of extracted nuprl
> programs)
> 
> Cheers,
> Frédéric Gava
> 
> ----- Original Message -----
> From: "Roberto Bagnara" <bagnara@cs.unipr.it>
> To: <caml-list@inria.fr>
> Sent: Thursday, December 02, 2004 12:57 PM
> Subject: [Caml-list] Automatic complexity analysis of OCaml programs
> 
> 
> >
> > I am looking for references and pointers to existing
> > works concerning the automatic or semiautomatic
> > complexity analysis of programs written in OCaml or
> > in a subset of it.  Pointers to the literature
> > and to available implementations are both very welcome.
> > Many thanks in advance,
> >
> >      Roberto
> >
> > --
> > Prof. Roberto Bagnara
> > Computer Science Group
> > Department of Mathematics, University of Parma, Italy
> > http://www.cs.unipr.it/~bagnara/
> > mailto:bagnara@cs.unipr.it
> >
> > _______________________________________________
> > Caml-list mailing list. Subscription management:
> > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> > Archives: http://caml.inria.fr
> > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> > Bug reports: http://caml.inria.fr/bin/caml-bugs
> >
> 
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs