Equivalence of free Boolean graphs can be decided probabilistically in polynomial time

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

zbMATH Keywords

Boolean functionsdirected acyclic graphsrandom polynomial timeequivalence of free Boolean graphsIanov schemes

Mathematics Subject Classification ID

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

• Binary Decision Diagrams
• On Ianov's Program Schemata
• Unnamed Item
• Unnamed Item