Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
From MaRDI portal
Publication:1144943
DOI10.1016/S0020-0190(80)90078-2zbMath0444.68059OpenAlexW2014064621MaRDI QIDQ1144943
Ashok K. Chandra, Mark N. Wegman, Manuel Blum
Publication date: 1980
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(80)90078-2
Boolean functionsdirected acyclic graphsrandom polynomial timeequivalence of free Boolean graphsIanov schemes
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs, A linear time equivalence test for read-twice DNF formulas, Efficient data structures for Boolean functions, On approximation by \(^{\oplus}\)-OBDDs, On the complexity of constructing optimal ordered binary decision diagrams, Unnamed Item, Learning from examples with unspecified attribute values., Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, Unnamed Item, Graph driven BDDs -- a new data structure for Boolean functions, Probabilistic verification of Boolean functions, A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy, Deterministically testing sparse polynomial identities of unbounded degree, Monotone term decision lists, Unnamed Item, Decision tree approximations of Boolean functions
Cites Work
