On the descriptive and algorithmic power of parity ordered binary decision diagrams

DOI10.1007/BFB0023460MaRDI QIDQ5047172zbMATH OpenOpenAlexFDO

Authors Stephan Waack

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0023460

Mathematics Subject Classification ID

Data structures (68P05) Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• scientific article; zbMATH DE number 1759434
• On the complexity of constructing optimal ordered binary decision diagrams
• Ordered binary decision diagrams, pigeonhole formulas and beyond
• Ordered binary decision diagrams and the Davis-Putnam procedure
• On random orderings of variables for parity ordered binary decision diagrams
• scientific article; zbMATH DE number 474728
• On the minimization of (complete) ordered binary decision diagrams
• Ordered binary decision diagrams and minimal trellises

Cites work

• Efficient data structures for Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4213443 (Why is no real title available?)
• Lower bounds on the complexity of real-time branching programs
• On oblivious branching programs of linear length
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Reduction of OBDDs in linear time

Cited in

(11)

• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Decision procedures for inductive Boolean functions based on alternating automata
• Linear codes are hard for oblivious read-once parity branching programs
• Lower bounds for linearly transformed OBDDs and FBDDs
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Parity OBDDs cannot be handled efficiently enough
• scientific article; zbMATH DE number 1324659 (Why is no real title available?)
• scientific article; zbMATH DE number 1759434 (Why is no real title available?)
• scientific article; zbMATH DE number 1834649 (Why is no real title available?)
• Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
• Algebraic proofs over noncommutative formulas

This page was built for publication: On the descriptive and algorithmic power of parity ordered binary decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5047172)