From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 42816BC2F for ; Thu, 2 Dec 2004 16:21:26 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id iB2FLP9N011695 for ; Thu, 2 Dec 2004 16:21:25 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA14520 for ; Thu, 2 Dec 2004 16:21:25 +0100 (MET) Received: from cgpsrv2.cis.mcmaster.ca (cgpsrv2.CIS.McMaster.CA [130.113.64.62]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id iB2FLORq015327 for ; Thu, 2 Dec 2004 16:21:24 +0100 Received: from [24.43.193.126] (account carette@univmail.cis.mcmaster.ca) by cgpsrv2.cis.mcmaster.ca (CommuniGate Pro WebUser 4.1.8) with HTTP id 74863986; Thu, 02 Dec 2004 10:21:23 -0500 From: "Jacques Carette" Subject: Re: [Caml-list] Automatic complexity analysis of OCaml programs To: =?ISO-8859-1?Q?Fr=E9d=E9ric?= Gava , "Roberto Bagnara" , X-Mailer: CommuniGate Pro WebUser Interface v.4.1.8 Date: Thu, 02 Dec 2004 10:21:23 -0500 Message-ID: In-Reply-To: <003101c4d87f$9ec0d3e0$0100a8c0@mshome.net> MIME-Version: 1.0 Content-Type: text/plain; charset="ISO-8859-1"; format="flowed" Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 41AF32F5.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 41AF32F4.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 ocaml:01 flajolet:01 salvy:01 gava:01 gava:01 wrote:01 inference:01 bernd:01 metayer:01 mads:01 cheers:01 caml-list:01 pointers:01 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: 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 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" > To: > 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