On the composition problem for OBDDs with multiple variable orders
Identifieur interne : 002285 ( Main/Exploration ); précédent : 002284; suivant : 002286On the composition problem for OBDDs with multiple variable orders
Auteurs : Anna Slobodová [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Abstract: Ordered Binary Decision Diagram (OBDD) is a favorite data structure used for representation Boolean functions in computer-aided synthesis and verification of digital systems. The secret of its success is the efficiency of the algorithms for Boolean operations, satisfiability and equivalence check. However, the algorithms work well under condition only that the variable order of considered OBDDs is the same. In this paper, we discuss the problem of Boolean operations on OBDDs with multiple variable orders, which naturally appears, e.g., in the connection with minimization techniques based on dynamic variable reordering. Our goal is to place the problem with respect to its complexity and to point out the difficulties in finding an acceptable solution.
Url:
DOI: 10.1007/BFb0055815
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001005
- to stream Istex, to step Curation: 000E95
- to stream Istex, to step Checkpoint: 000E56
- to stream Main, to step Merge: 002674
- to stream PascalFrancis, to step Corpus: 001111
- to stream PascalFrancis, to step Curation: 001714
- to stream PascalFrancis, to step Checkpoint: 000E79
- to stream Main, to step Merge: 002750
- to stream Main, to step Curation: 002285
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the composition problem for OBDDs with multiple variable orders</title><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:2C1D19692E8B185716E2FE9D016EE0716E41847C</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/BFb0055815</idno><idno type="url">https://api.istex.fr/document/2C1D19692E8B185716E2FE9D016EE0716E41847C/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001005</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001005</idno><idno type="wicri:Area/Istex/Curation">000E95</idno><idno type="wicri:Area/Istex/Checkpoint">000E56</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E56</idno><idno type="wicri:doubleKey">0302-9743:1998:Slobodova A:on:the:composition</idno><idno type="wicri:Area/Main/Merge">002674</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:98-0427282</idno><idno type="wicri:Area/PascalFrancis/Corpus">001111</idno><idno type="wicri:Area/PascalFrancis/Curation">001714</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000E79</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000E79</idno><idno type="wicri:doubleKey">0302-9743:1998:Slobodova A:on:the:composition</idno><idno type="wicri:Area/Main/Merge">002750</idno><idno type="wicri:Area/Main/Curation">002285</idno><idno type="wicri:Area/Main/Exploration">002285</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the composition problem for OBDDs with multiple variable orders</title><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodová">Anna Slobodová</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institute of Telematics, Trier</wicri:regionArea><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">2C1D19692E8B185716E2FE9D016EE0716E41847C</idno><idno type="DOI">10.1007/BFb0055815</idno><idno type="ChapterID">62</idno><idno type="ChapterID">Chap62</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm complexity</term><term>Binary decision diagram</term><term>Boolean function</term><term>Combinatorial problem</term><term>Computer theory</term><term>NP hard problem</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Complexité algorithme</term><term>Diagramme binaire décision</term><term>Fonction booléenne</term><term>Informatique théorique</term><term>Problème NP difficile</term><term>Problème combinatoire</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Ordered Binary Decision Diagram (OBDD) is a favorite data structure used for representation Boolean functions in computer-aided synthesis and verification of digital systems. The secret of its success is the efficiency of the algorithms for Boolean operations, satisfiability and equivalence check. However, the algorithms work well under condition only that the variable order of considered OBDDs is the same. In this paper, we discuss the problem of Boolean operations on OBDDs with multiple variable orders, which naturally appears, e.g., in the connection with minimization techniques based on dynamic variable reordering. Our goal is to place the problem with respect to its complexity and to point out the difficulties in finding an acceptable solution.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodová">Anna Slobodová</name></noRegion><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/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002285 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002285 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:2C1D19692E8B185716E2FE9D016EE0716E41847C
|texte= On the composition problem for OBDDs with multiple variable orders
}}
| This area was generated with Dilib version V0.6.31. |  |