Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds

Henrik Brosenne, Matthias Homeister and Stephan Waack

View Related Documents

Book Chapter
On the descriptive and algorithmic power of parity ordered binary decision diagrams
Stephan Waack
Lecture Notes in Computer Science, 1997, Volume 1200, STACS 97, Pages 201-212
- Download PDF (633.6 KB)
Journal Article
On WLCDs and the Complexity of Word-Level Decision Diagrams—A Lower Bound for Division
Christoph Scholl, Bernd Becker and Thomas Weis
Formal Methods in System Design, 2002, Volume 20, Number 3, Pages 311-326
- Download PDF (220.7 KB)
Book Chapter
Manipulation algorithms for K^*BMDs
Rolf Drechsler, Bernd Becker and Stefan Ruppertz
Lecture Notes in Computer Science, 1997, Volume 1217, Tools and Algorithms for the Construction and Analysis of Systems, Pages 4-18
- Download PDF (684.7 KB)
Book Chapter
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications
Extended Abstract
Beate Bollig and Philipp Woelfel
Lecture Notes in Computer Science, 2002, Volume 2420, Mathematical Foundations of Computer Science 2002, Pages 131-142
- Download PDF (196.8 KB)
Book Chapter
New lower bounds and hierarchy results for restricted branching programs
Detlef Sieling and Ingo Wegener
Lecture Notes in Computer Science, 1995, Volume 903, Graph-Theoretic Concepts in Computer Science, Pages 359-370
- Download PDF (762.8 KB)
Book Chapter
On the relation between BDDs and FDDs
Extended abstract
Bernd Becker, Rolf Drechsler and Ralph Werchner
Lecture Notes in Computer Science, 1995, Volume 911, LATIN '95: Theoretical Informatics, Pages 72-83
- Download PDF (680.2 KB)
Book Chapter
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
Extended Abstract
Beate Bollig
Lecture Notes in Computer Science, 2000, Volume 1893, Mathematical Foundations of Computer Science 2000, Pages 222-231
- Download PDF (158.3 KB)
Book Chapter
The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions
Ingo Wegener
Lecture Notes in Computer Science, 1994, Volume 790, Graph-Theoretic Concepts in Computer Science, Pages 252-263
- Download PDF (623.4 KB)
Book Chapter
A View from the Engine Room: Computational Support for Symbolic Model Checking
Randal E. Bryant
Lecture Notes in Computer Science, 2008, Volume 5000, 25 Years of Model Checking, Pages 145-149
- Download PDF (253.3 KB)
Book Chapter
Ordered Binary Decision Diagrams and the Davis-Putnam procedure
Tomás E. Uribe and Mark E. Stickel
Lecture Notes in Computer Science, 1994, Volume 845, Constraints in Computational Logics, Pages 34-49
- Download PDF (1.0 MB)

Abstract

We investigate graph-driven free parity BDDs, which strictly generalize the two well-known models parity OBDDs and graph-driven free BDDs.

The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven free parity BDD. The second main result is an exponential lower bound on the size of graph-driven free parity BDD for linear code functions.

Supported by DFG grant Wa766/4-1

Supported in part by DFG grant Wa766/4-1

Fulltext Preview

Image of the first page of the fulltext document

Frequently asked questions General info on journals and books Send us your feedback Impressum Contact us

SpringerLink

Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds

View Related Documents

Abstract

Fulltext Preview