From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA22085; Wed, 1 Aug 2001 15:42:59 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA22080 for ; Wed, 1 Aug 2001 15:42:58 +0200 (MET DST) Received: from heplix4.ikp.physik.tu-darmstadt.de (heplix4.ikp.physik.tu-darmstadt.de [130.83.210.158]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f71DgwX23307 for ; Wed, 1 Aug 2001 15:42:58 +0200 (MET DST) Received: (from ohl@localhost) by heplix4.ikp.physik.tu-darmstadt.de (8.11.2/8.11.2/SuSE Linux 8.11.1-0.5) id f71Dfl527634; Wed, 1 Aug 2001 15:41:47 +0200 From: Thorsten Ohl MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15208.1819.257638.641407@heplix4.ikp.physik.tu-darmstadt.de> Date: Wed, 1 Aug 2001 15:41:47 +0200 To: caml-list@inria.fr Subject: [Caml-list] "super-compaction" of values In-Reply-To: <20010801122051.A12317@kastanie.ai.univie.ac.at> References: <20010801122051.A12317@kastanie.ai.univie.ac.at> X-Mailer: VM 6.84 under Emacs 20.7.1 Reply-To: ohl@hep.tu-darmstadt.de Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Markus Mottl writes: > has anybody already attempted to implement some kind of > "super-compaction" [...] If this worked for arbitrary > datastructures, one could exploit this to produce very compact > representations of values by maximizing the amount of sharing > between them. I'm sure that one can not beat the combinatorial complexity of the general case. For example, I work with algebraic expressions that grow in size like (2n-1)!! = (2n-1)(2n-3)(2n-5)... if represented as trees, but can be rewritten as DAGs of size 10**(n/2) [see http://heplix.ikp.physik.tu-darmstadt.de/~ohl/omega/ and in particular the chapter Directed Acyclical Graphs in http://heplix.ikp.physik.tu-darmstadt.de/~ohl/omega/omega.pdf]. In my experience, one can beat the combinatorial complexity only if one understands the genesis of such values with high sharing potential. Then one can construct algorithms that start from building all possible combinations in a highly condensed representation and select the interesting ones later. This will be much more efficient than building only the interesting ones and searching for shared nodes later. But this is never a general solution, because it requires a good unterstanding of the structure of possible terms. -- Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here] ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr