From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.6 required=5.0 tests=NO_REAL_NAME autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 9B434BBAF for ; Fri, 27 Mar 2009 11:25:58 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkIBAJdGzEmCT8ibnGdsb2JhbACUZSJ5AQEBAQEICwgJEbgpg3cG X-IronPort-AV: E=Sophos;i="4.38,431,1233529200"; d="scan'208";a="25092668" Received: from mailhost.u-strasbg.fr ([130.79.200.155]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 27 Mar 2009 11:25:58 +0100 Received: from localhost (gengis.u-strasbg.fr [130.79.200.60]) by mailhost.u-strasbg.fr (8.14.2/jtpda-5.5pre1) with ESMTP id n2RAPvBW077731 ; Fri, 27 Mar 2009 11:25:57 +0100 (CET) Received: from turing6.u-strasbg.fr (turing6.u-strasbg.fr [2001:660:4701:2001::100]) by webmail.u-strasbg.fr (Horde MIME library) with HTTP; Fri, 27 Mar 2009 11:25:57 +0100 Message-ID: <20090327112557.fgh38vjcmc8g80og@webmail.u-strasbg.fr> Date: Fri, 27 Mar 2009 11:25:57 +0100 From: David.Bulone@ulp.u-strasbg.fr To: caml-list@inria.fr Cc: tajine@dpt-info.u-strasbg.fr, violard@icps.u-strasbg.fr Subject: =?iso-8859-1?b?UuljdXJzaXZpdOk=?= terminale / tail-recursivity MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: quoted-printable User-Agent: Internet Messaging Program (IMP) H3 (4.1.5) / FreeBSD-6.2 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.0.1 (mailhost.u-strasbg.fr [130.79.200.155]); Fri, 27 Mar 2009 11:25:57 +0100 (CET) X-Virus-Scanned: ClamAV 0.94.2/9173/Fri Mar 27 05:51:01 2009 on mr5.u-strasbg.fr X-Virus-Status: Clean X-Spam: no; 0.00; u-strasbg:01 terminale:01 recursives:01 recursives:01 undecidable:01 stack:01 stack:01 functions:01 functions:01 probleme:03 size:95 transform:05 problem:05 probably:07 classes:08 Bonjour, Y'a-t-il dans la litt=E9rature des r=E9sultats sur la transformation =20 automatique de d=E9finitions r=E9cursives non terminales, en d=E9finitions = =20 de fonctions r=E9cursives terminales avec pile de taille born=E9e ? Sachant que le probl=E8me g=E9n=E9ral est certainement ind=E9cidable, = =20 y'a-t-il des classes de fonctions pour lesquelles on sait faire cette =20 tranformation ? (par exemple, cette transformation est possible avec fibonacci et une =20 pile de taille 2). Je travaille actuellement sur ce th=E8me dans le cadre d'un TER. Merci pour vos r=E9ponses. ----------------------------------------------------------------------------= ------ Hello, Is there in the literature some results about the automatic =20 transformation of non tail-recursive functions definitions, into =20 tail-recursive ones using a bounding stack ? The general problem is probably undecidable. But maybe there is =20 some family of functions for which we know how to transform. (for example, the transformation is possible for fibonacci sequence =20 and a stack of size 2). I'm currently Master student (TER) working on that. Thanks for yours responses.