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

DOI10.1007/BFb0023460zbMath1498.68108OpenAlexW1495086092MaRDI QIDQ5047172

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

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

Related Items

Parity OBDDs cannot be handled efficiently enough, Algebraic proofs over noncommutative formulas, Linear codes are hard for oblivious read-once parity branching programs, Lower bounds for linearly transformed OBDDs and FBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• On oblivious branching programs of linear length
• Reduction of OBDDs in linear time
• Efficient data structures for Boolean functions
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• Lower bounds on the complexity of real-time branching programs