Publication
Information Processing Letters
Paper

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

View publication

Abstract

Natural graphical representations for Boolean functions, so-called free Boolean graphs, arise in the study of Ianov schemes. Fortune, Hopcroft and Schmidt have asked if an algorithm can decide covalence of these free Boolean graphs in poly- time. We show that random polynomial time will suffice.

Date

Publication

Information Processing Letters

Authors

Topics

Share