Zur Kurzanzeige

1999-05-03Dissertation DOI: 10.18452/14357
Binary Decision Diagrams for Random Boolean Functions
dc.contributor.authorGröpl, Clemens
dc.date.accessioned2017-06-18T03:25:01Z
dc.date.available2017-06-18T03:25:01Z
dc.date.created1999-05-03
dc.date.issued1999-05-03
dc.identifier.urihttp://edoc.hu-berlin.de/18452/15009
dc.description.abstractBinary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können.ger
dc.description.abstractBinary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectBinäres Entscheidungsdiagrammger
dc.subjectBoolesche Funktionger
dc.subjectprobabilistische Analyseger
dc.subjectShannon Effektger
dc.subjectBinary decision diagrameng
dc.subjectBoolean functioneng
dc.subjectprobabilistic analysiseng
dc.subjectShannon effecteng
dc.subject.ddc004 Informatik
dc.titleBinary Decision Diagrams for Random Boolean Functions
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-1008985
dc.identifier.urnurn:nbn:de:kobv:11-1008996
dc.identifier.doihttp://dx.doi.org/10.18452/14357
dc.date.accepted1999-05-03
dc.contributor.refereeSrivastav, Anand
dc.contributor.refereePrömel, Hans Jürgen
dc.contributor.refereeWegener, Ingo
dc.subject.dnb28 Informatik, Datenverarbeitung
dc.subject.rvkSK 150
local.edoc.pages126
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät II

Zur Kurzanzeige