Lower bounds for linearly transformed OBDDs and FBDDs

DOI10.1006/JCSS.2001.1818zbMath1013.68131OpenAlexW2050386913MaRDI QIDQ1608325

Detlef Sieling

Publication date: 4 August 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8881d2e40f88fdf8525c33a606d45d501725bfb1

zbMATH Keywords

linearly transformed ordered binary decision diagrams

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple function that requires exponential size read-once branching programs
• On the computational power of linearly transformed BDDs
• On the size of binary decision diagrams representing Boolean functions
• Graph driven BDDs -- a new data structure for Boolean functions
• Entropy of contact circuits and lower bounds on their complexity
• Neither reading few bits twice nor reading illegally helps much
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Linear codes are hard for oblivious read-once parity branching programs
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Binary decision tree test functions
• A note on read-$k$ times branching programs
• Communication Complexity
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Separating counting communication complexity classes

This page was built for publication: Lower bounds for linearly transformed OBDDs and FBDDs