In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.

PropertyValue
dbpprop:abstract
  • In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.
  • Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt.
  • Un diagramme de décision binaire (BDD pour Binary Decision Diagram en anglais), comme une forme normale niée ou un graphe orienté acyclique propositionnel, est une structure de données utilisée pour représenter des fonctions booléennes. Une fonction booléenne peut être représentée par un graphe orienté acyclique avec une racine consistant en nœuds de décisions, et deux nœuds terminaux appelés 0-terminal et 1-terminal. Chaque nœud de décision est étiqueté par une variable booléenne et a deux nœuds fils, appelés fils bas et fils haut. L'arête d'un nœud à un fils bas (resp. haut) représente l'affectation de la variable à 0 (resp. 1). Un tel BBD est appelé « ordonné » si toutes les variables apparaissent dans le même ordre sur tous les chemins depuis la racine vers les nœuds terminaux. Il est appelé « réduit » si le graphe est réduit selon deux règles : – tous les sous-graphes isomorphes ont une représentation unique; – tous les nœuds dont les deux fils sont isomorphes sont éliminés. Dans son usage courant, le terme diagramme de décision binaire réfère pratiquement tout le temps à un diagramme de décision binaire ordonné réduit (ROBDD pour Reduced Ordered Binary Decision Diagram). L'avantage d'un ROBDD est qu'il est canonique (unique) pour une fonction booléenne donnée. Cette propriété le rend utile, par exemple, pour la vérification d'équivalence fonctionnelle (qui se traduit par l'égalité des ROBDD associés, laquelle peut être évaluée en temps constant). Un chemin de la racine au nœud 1-terminal représente une affectation de variable (partielle ou pas) pour laquelle la fonction booléenne représentée est vraie. Quand le chemin descend d'un nœud vers un fils bas (resp. fils haut), on affecte à la variable représentée par ce nœud la valeur 0 (resp. 1). Les diagrammes de décision binaires sont très utilisés par les programmes de conception assistée par ordinateur (CAD) pour générer des circuits (synthèse logique), et dans la vérification formelle.
  • 二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。
dbpprop:date
  • August 2009
dbpprop:doiInlineProperty
  • 10.1109/12.537122
  • Improving the Variable Ordering of OBDDs Is NP-Complete
dbpprop:hasPhotoCollection
dbpprop:reason
  • please give reference; I would like to know these heuristics!
dbpprop:reference
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.
  • Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt.
  • Un diagramme de décision binaire (BDD pour Binary Decision Diagram en anglais), comme une forme normale niée ou un graphe orienté acyclique propositionnel, est une structure de données utilisée pour représenter des fonctions booléennes. Une fonction booléenne peut être représentée par un graphe orienté acyclique avec une racine consistant en nœuds de décisions, et deux nœuds terminaux appelés 0-terminal et 1-terminal.
  • 二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。
rdfs:label
  • Binary decision diagram
  • Binäres Entscheidungsdiagramm
  • Diagramme de décision binaire
  • 二分決定図
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of