dc.contributor.advisor | Waack, Stephan Prof. Dr. | de |
dc.contributor.author | Brosenne, Henrik | de |
dc.date.accessioned | 2006-08-15T15:26:55Z | de |
dc.date.accessioned | 2013-01-18T13:24:58Z | de |
dc.date.available | 2013-01-30T23:50:56Z | de |
dc.date.issued | 2006-08-15 | de |
dc.identifier.uri | http://hdl.handle.net/11858/00-1735-0000-0006-B380-E | de |
dc.identifier.uri | http://dx.doi.org/10.53846/goediss-2588 | |
dc.description.abstract | Eine Boolesche Funktion wird einer Komplexitätsklasse zugeordnet, über die oberen und unteren Schranken des Ressourcenverbrauchs bei ihrer Berechnung in einem festen Berechungsmodell. Deshalb wird nach Methoden zur Bestimmung von oberen und unteren Schranken für die Größe von eingeschränkten Branchingprogrammen gesucht.Intensiv studiert wurden Branchingprogramme mit einmaligen geordneten Tests (OBDDs) und Parity-Akzeptierungsmodus. Der Parity-Akzeptierungsmodus und die Forderung nach einmaligen geordneten Tests erlaubt es, die Komplexität einer Booleschen Funktion, die mit OBDDs dargestellt werden sollen, mit Mitteln der linearen Algebra zu beschreiben. Diese Methode wird auf graphgesteuerte und wohlstrukturierte graphgesteuerte Branchingprogramme angewendet, bei denen das Lesen der Eingabe durch einen speziellen Graphen reglementiert wird. Aus der algebraischen Beschreibung wird ein Kriterium für untere Schranken abgeleitet, mit dessen Hilfe superpolynomielle untere Schranken für diese beiden Modelle bewiesen werden.Die Verwendung von arithmetischen OBDDs über Halbringen, von denen alle betrachteten OBDDs Spezialfälle sind, ermöglicht es, alle Akzeptierungsmodi gleichzeitig zu betrachten und Ergebnisse aus der Algebra auf OBDDs anzuwenden.Nichtdeterministische OBDDs mit Parity- und existenziellem Akzeptierungsmodus sind unvergleichbar. Es gibt Funktionen, die jeweils von OBDDs mit dem einen Akzeptierungsmodus in polynomieller Größe darstellbar sind, aber für die es nur OBDDs exponentieller Größe mit dem anderen Akzeptierungsmodus gibt. Es wird gezeigt, dass bezüglich der Approximation nichtdeterministische OBDDs mit Parity-Akzeptierungsmodus stärker sein könnten. Für jede Funktion, die von einem nichtdeterministischen OBDD quasipolynomieller Größe mit existenziellem Akzeptierungsmodus dargestellt werden kann, gibt es ein nichtdeterministisches OBDD gleicher Größenordnung mit Parity-Akzeptierungsmodus, das dieselbe Funktion darstellt, bis auf einen kleinen Anteil aller Eingaben.Eine Möglichkeit die Darstellungskraft von OBDDs zu vergrößern, ist mehrfache Tests der Eingabe zuzulassen. OBDDs mit k-fachen Tests erlauben das k-fache Lesen der Eingabe, allerdings immer in derselben Reihenfolge. Für die Darstellungskraft von deterministischen OBDDs mit k-fachen Tests gibt es eine strenge Hierarchie. Es wird gezeigt, dass konstant viele mehrfache Tests weder für nichtdeterministische OBDDs mit existenziellem, universellem oder Parity-Akzeptierungsmodus noch für randomisierte OBDDs zu einer größeren Darstellungskraft führen. | de |
dc.format.mimetype | application/pdf | de |
dc.language.iso | ger | de |
dc.rights.uri | http://webdoc.sub.gwdg.de/diss/copyr_diss.html | de |
dc.title | Obere und untere Schranken für eingeschränkte Parity-Branchingprogramme | de |
dc.type | doctoralThesis | de |
dc.title.translated | Upper and Lower Bounds for Restricted Parity Branching Programs | de |
dc.contributor.referee | Waack, Stephan Prof. Dr. | de |
dc.date.examination | 2006-04-18 | de |
dc.subject.dnb | 004 Informatik | de |
dc.description.abstracteng | Boolean Functions are classified in complexity classes by the upper and lower bounds of the resources a computation required to solve the function in a certain computation model.Thus one is interested in upper and lower bound for the size of restricted branching programs.Ordered binary decision diagrams (OBDDs) with parity acceptance mode are intensely studied. The characterizing of boolean functions computed by OBDDs in terms of the linear algebra is possible because of the parity acceptance mode and the global variable ordering. This idea is applicable on graphdriven and wellstructured graphdriven branching programs too. In these models the input is read according to a graphordering. The algebraic characterization of this two models leads to a method to prove superpolynomial lower bounds, respectively.Arithmetic OBDDs on semi rings generalize the other considered models. So all modes of acceptance can observed at once and results from algebra are usable for OBDDs.Nondeterministic OBDDs with parity and existential acceptance mode are incomparable. Some functions with polynomial size OBDDs of one type require exponential size OBDDs of the other type. It is shown that nevertheless OBDDs with parity acceptance mode might be stronger with respect to approximation.For every function computable by an OBDD with existential acceptance mode of quasipolynomial size there is an OBDD with parity acceptance mode that computes the same function on all but a small fraction of the inputs.OBDDs with repeated tests improve OBDDs. OBDD with k layers are testing the input k-times but always in the same order. A tight hierarchy is known for the class of functions representable by deterministic OBDDs with k layers. For k being a constant, it is shown that for the existential, the universal, the parity, and the randomized acceptance mode the analogous hierarchy collapses. | de |
dc.contributor.coReferee | Damm, Carsten Prof. Dr. | de |
dc.subject.topic | Mathematics and Computer Science | de |
dc.subject.ger | Branchingprogramme | de |
dc.subject.ger | BPs | de |
dc.subject.ger | untere Schranken | de |
dc.subject.ger | obere Schranken | de |
dc.subject.ger | arithmetische BPs | de |
dc.subject.eng | branching programs | de |
dc.subject.eng | BPs | de |
dc.subject.eng | upper bounds | de |
dc.subject.eng | lower bounds | de |
dc.subject.eng | arithmetic BPs | de |
dc.subject.bk | 54.10 | de |
dc.identifier.urn | urn:nbn:de:gbv:7-webdoc-1266-6 | de |
dc.identifier.purl | webdoc-1266 | de |
dc.affiliation.institute | Fakultät für Mathematik und Informatik | de |
dc.subject.gokfull | AH | de |
dc.identifier.ppn | 517948915 | de |