Global rebuilding of OBDDs avoiding memory requirement maxima
Identifieur interne : 000290 ( LNCS/Analysis ); précédent : 000289; suivant : 000291Global rebuilding of OBDDs avoiding memory requirement maxima
Auteurs : Jochen Bern [Allemagne] ; Christoph Meinel [Allemagne] ; Anna Slobodová [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1995.
Abstract
Abstract: It is well-known that the size of an ordered binary decision diagram (OBDD) may depend crucially on the order in which the variables occur. In the paper, we describe an implementation of an outputefficient algorithm that transforms an OBDD P representing a Boolean function f with respect to one variable ordering π into an OBDD Q that represents f with respect to another variable ordering σ. The algorithm runs in average time O(¦P∥Q¦) and requires O(¦P¦+n¦Q¦) space. The importance of the algorithm is demonstrated by means of experimental results on basically two different applications. In one of them, the algorithm is used merely once. Such transformations are needed to test equivalence or to perform synthesis on OBDDs in which variables appear in different orders. The other application shows a way how to decrease the size of intermediate representations in the course of the construction of OBDDs from a given circuit. Here the algorithm is used dynamically, whenever the size of the manipulated OBDDs becomes too large.
Url:
DOI: 10.1007/3-540-60045-0_36
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001234
- to stream Istex, to step Curation: 001122
- to stream Istex, to step Checkpoint: 001158
- to stream Main, to step Merge: 002E63
- to stream Main, to step Curation: 002959
- to stream Main, to step Exploration: 002959
- to stream LNCS, to step Extraction: 000290
Links to Exploration step
ISTEX:5D5A86C8E465CA1550E5C48D995BD6ED6645839ALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Global rebuilding of OBDDs avoiding memory requirement maxima</title><author><name sortKey="Bern, Jochen" sort="Bern, Jochen" uniqKey="Bern J" first="Jochen" last="Bern">Jochen Bern</name></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodová">Anna Slobodová</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:5D5A86C8E465CA1550E5C48D995BD6ED6645839A</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1007/3-540-60045-0_36</idno><idno type="url">https://api.istex.fr/document/5D5A86C8E465CA1550E5C48D995BD6ED6645839A/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001234</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001234</idno><idno type="wicri:Area/Istex/Curation">001122</idno><idno type="wicri:Area/Istex/Checkpoint">001158</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001158</idno><idno type="wicri:doubleKey">0302-9743:1995:Bern J:global:rebuilding:of</idno><idno type="wicri:Area/Main/Merge">002E63</idno><idno type="wicri:Area/Main/Curation">002959</idno><idno type="wicri:Area/Main/Exploration">002959</idno><idno type="wicri:Area/LNCS/Extraction">000290</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Global rebuilding of OBDDs avoiding memory requirement maxima</title><author><name sortKey="Bern, Jochen" sort="Bern, Jochen" uniqKey="Bern J" first="Jochen" last="Bern">Jochen Bern</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Trier, D-54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName></affiliation></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Trier, D-54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodová">Anna Slobodová</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Trier, D-54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1995</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">5D5A86C8E465CA1550E5C48D995BD6ED6645839A</idno><idno type="DOI">10.1007/3-540-60045-0_36</idno><idno type="ChapterID">2</idno><idno type="ChapterID">Chap2</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: It is well-known that the size of an ordered binary decision diagram (OBDD) may depend crucially on the order in which the variables occur. In the paper, we describe an implementation of an outputefficient algorithm that transforms an OBDD P representing a Boolean function f with respect to one variable ordering π into an OBDD Q that represents f with respect to another variable ordering σ. The algorithm runs in average time O(¦P∥Q¦) and requires O(¦P¦+n¦Q¦) space. The importance of the algorithm is demonstrated by means of experimental results on basically two different applications. In one of them, the algorithm is used merely once. Such transformations are needed to test equivalence or to perform synthesis on OBDDs in which variables appear in different orders. The other application shows a way how to decrease the size of intermediate representations in the course of the construction of OBDDs from a given circuit. Here the algorithm is used dynamically, whenever the size of the manipulated OBDDs becomes too large.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Bern, Jochen" sort="Bern, Jochen" uniqKey="Bern J" first="Jochen" last="Bern">Jochen Bern</name></region><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodová">Anna Slobodová</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000290 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000290 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:5D5A86C8E465CA1550E5C48D995BD6ED6645839A
|texte= Global rebuilding of OBDDs avoiding memory requirement maxima
}}
| This area was generated with Dilib version V0.6.31. |  |