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.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id F0FB6BBCA for ; Tue, 1 Apr 2008 17:55:26 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtwAALX38UfPn3g9o2dsb2JhbACBWo9vAQEBAQEBBwUJBxaaAQ X-IronPort-AV: E=Sophos;i="4.25,588,1199660400"; d="scan'208";a="10281806" Received: from nn7.excitenetwork.com (HELO excite.com) ([207.159.120.61]) by mail1-smtp-roc.national.inria.fr with ESMTP; 01 Apr 2008 17:55:26 +0200 Received: by xprdmxin.myway.com (Postfix, from userid 110) id F1CE08B34A; Tue, 1 Apr 2008 11:55:24 -0400 (EDT) To: caml-list@yquem.inria.fr Subject: More efficient implementation of intersection of sets? Received: from [132.230.166.192] by xprdmailfe18.nwk.excite.com via HTTP; Tue, 01 Apr 2008 11:55:24 EST X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: ID = 8a8a82c06e1c8d4366ddc3f449c5aa61 Reply-To: sasha.mal@excite.com From: "sasha mal" MIME-Version: 1.0 X-Sender: sasha.mal@excite.com X-Mailer: PHP Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Message-Id: <20080401155524.F1CE08B34A@xprdmxin.myway.com> Date: Tue, 1 Apr 2008 11:55:24 -0400 (EDT) X-Spam: no; 0.00; intersection:01 ocaml:01 runtime:01 intersection:01 ocaml:01 frisch:01 frisch:01 bdds:01 bdds:01 implements:01 excite:98 excite:98 wrote:01 wrote:01 recursively:01 Dear OCaml users! Currently, Set.inter x y splits y into two trees, one containing elements that are bigger and the other containing elements that are smaller than the top of x, then applies the procedure recursively. What is the exact runtime of the algorithm? Is there a better one for the intersection for OCaml sets? Regards Sasha --- On Fri 03/14, Alain Frisch < alain@frisch.fr > wrote: From: Alain Frisch [mailto: alain@frisch.fr] To: sasha.mal@excite.com Cc: caml-list@yquem.inria.fr Date: Fri, 14 Mar 2008 08:38:41 +0100 Subject: Re: [Caml-list] BDDs in ocaml sasha mal wrote:> I wonder whether anyone has a BDD (binary decision diagram)> implementation in ocaml. Ocaml interfaces to external BDD> implementations in other languages (like Cudd) are of no use to me.I've seen many implementation of BDDs in OCaml, but none of them implements automatic reordering of variables (which is by far the most complex part of serious BDD packages). For some applications, this is really a must. Why is it impossible for you to use to an external BDD implementation?-- Alain _______________________________________________ Join Excite! - http://www.excite.com The most personalized portal on the Web!