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

Laurent Mauborgne

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: [phone]; 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

Sujets

• Time complexity

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 13
• Langue: English

Extrait

ImprovingtheRepresentationofInfiniteTrees toDealwithSetsofTrees LaurentMauborgne LIENS–DMI,E ´ coleNormaleSupe´rieure,45rued’Ulm,75230Pariscedex05,France Tel:[phone];Email: [e-mail] WWWhomepage: http://www.dmi.ens.fr/~mauborgn/ Abstract.Inordertodealefficientlywithinfiniteregulartrees(orother pointedgraphstructures),wegivenewalgorithmstostoresuchstruc- tures.Thetreesarestoredinsuchawaythattheirrepresentationis uniqueandsharesasmuchaspossible.Thismaximalsharingallows substantialmemorygainandspeedup.Forexample,equalitytesting becomesconstanttime.Thealgorithmsareincremental,andassuchal- lowgoodreactivebehavior.Thesenewalgorithmsarethenappliedto therepresentationofsetsoftrees.Theexpressivepowerofthisnewrep- resentationisexactlywhatisneededbyset-basedanalysis. 1Introduction Whenapplyingset-basedanalysistechniquesforpracticalapplications,oneis surprisedtoseethattherepresentationofthesetsoftreesisnotveryefficient. Evenwhenweusetreeautomata,wecannotovercomethisproblemwithout performingaminimizationofthewholeautomatonateachstep.Weproposea newwayofdealingwiththiskindofstructuretogetarepresentationthatisas smallaspossibleduringthecomputation. Afteranalysisoftheproblem,itappearsthattheunderlyingstructurewe wanttooptimizecanbedescribedmathematicallyasregularinfinitetrees.Be- causetreestructuresappeareverywhereincomputersciencewhereahierarchy occurs,wefounditinterestingtopresentthealgorithmsinanindependentway. Inthisway,ourtechniqueappearsasanextensionofanefficientsolutionto storefinitetrees. Therepresentationweextendusesjusttheminimumamountofmemoryby sharingequivalentsubtrees.Thissavesalotofspace.Itisused,forexample, withsetsofwordsrepresentedasatreetosharecommonprefixes.Itispossible tosharethesubtreesincrementally,andatthesametimetogiveaunique representationtodifferentversionsofthesametrees.Suchatechniqueallows constanttimeequalitytestingandagreatspeedupformanyotheralgorithms manipulatingtrees.IthasbeenthesourceofthesuccessofBinaryDecision Diagrams(BDDs)[2],whichareconsideredoneofthebestrepresentationsfor booleanfunctionssofar. Butassoonasaloopoccurssomewhereinthedata,finitetreetechniquesare nolongeradequate.Themaincontributionofthisarticleistoextendthegood