15 Pages
English

Improving the Representation of Infinite Trees to Deal with Sets of Trees

-

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Improving the Representation of Infinite Trees to Deal with Sets of Trees Laurent Mauborgne LIENS – DMI, Ecole Normale Superieure, 45 rue d'Ulm, 75 230 Paris cedex 05, France Tel: +33 (0) 1 44 32 20 66; Email: WWW home page: Abstract. In order to deal efficiently with infinite regular trees (or other pointed graph structures), we give new algorithms to store such struc- tures. The trees are stored in such a way that their representation is unique and shares as much as possible. This maximal sharing allows substantial memory gain and speed up. For example, equality testing becomes constant time. The algorithms are incremental, and as such al- low good reactive behavior. These new algorithms are then applied to the representation of sets of trees. The expressive power of this new rep- resentation is exactly what is needed by set-based analysis. 1 Introduction When applying set-based analysis techniques for practical applications, one is surprised to see that the representation of the sets of trees is not very efficient. Even when we use tree automata, we cannot overcome this problem without performing a minimization of the whole automaton at each step. We propose a new way of dealing with this kind of structure to get a representation that is as small as possible during the computation.

  • time equality testing

  • finite trees

  • technique allows constant

  • constant time

  • store

  • infinite trees

  • infinite regular

  • trees


Subjects

Informations

Published by
Reads 13
Language English
ImprovingtheRepresentationofInfiniteTreestoDealwithSetsofTreesLaurentMauborgneLIENSDMI,E´coleNormaleSupe´rieure,45ruedUlm,75230Pariscedex05,FranceTel:+33(0)144322066;Email:Laurent.Mauborgne@ens.frWWWhomepage:http://www.dmi.ens.fr/~mauborgn/Abstract.Inordertodealefficientlywithinfiniteregulartrees(orotherpointedgraphstructures),wegivenewalgorithmstostoresuchstruc-tures.Thetreesarestoredinsuchawaythattheirrepresentationisuniqueandsharesasmuchaspossible.Thismaximalsharingallowssubstantialmemorygainandspeedup.Forexample,equalitytestingbecomesconstanttime.Thealgorithmsareincremental,andassuchal-lowgoodreactivebehavior.Thesenewalgorithmsarethenappliedtotherepresentationofsetsoftrees.Theexpressivepowerofthisnewrep-resentationisexactlywhatisneededbyset-basedanalysis.1IntroductionWhenapplyingset-basedanalysistechniquesforpracticalapplications,oneissurprisedtoseethattherepresentationofthesetsoftreesisnotveryefficient.Evenwhenweusetreeautomata,wecannotovercomethisproblemwithoutperformingaminimizationofthewholeautomatonateachstep.Weproposeanewwayofdealingwiththiskindofstructuretogetarepresentationthatisassmallaspossibleduringthecomputation.Afteranalysisoftheproblem,itappearsthattheunderlyingstructurewewanttooptimizecanbedescribedmathematicallyasregularinfinitetrees.Be-causetreestructuresappeareverywhereincomputersciencewhereahierarchyoccurs,wefounditinterestingtopresentthealgorithmsinanindependentway.Inthisway,ourtechniqueappearsasanextensionofanefficientsolutiontostorefinitetrees.Therepresentationweextendusesjusttheminimumamountofmemorybysharingequivalentsubtrees.Thissavesalotofspace.Itisused,forexample,withsetsofwordsrepresentedasatreetosharecommonprefixes.Itispossibletosharethesubtreesincrementally,andatthesametimetogiveauniquerepresentationtodifferentversionsofthesametrees.Suchatechniqueallowsconstanttimeequalitytestingandagreatspeedupformanyotheralgorithmsmanipulatingtrees.IthasbeenthesourceofthesuccessofBinaryDecisionDiagrams(BDDs)[2],whichareconsideredoneofthebestrepresentationsforbooleanfunctionssofar.Butassoonasaloopoccurssomewhereinthedata,finitetreetechniquesarenolongeradequate.Themaincontributionofthisarticleistoextendthegood