scientific article; zbMATH DE number 4047617
[For the entire collection see Zbl 0608.00016.] \textit{R. E. Bryant} [IEEE Trans. Comput. C-35, 677-691 (1986; Zbl 0593.94022)] has presented a number of graph-theoretic algorithms for the manipulation of Boolean functions. The function is represented as a rooted directed acyclic graph. This is similar to the binary decision diagrams due to Lee and Akers, but Bryant has placed a restriction on the placement of the function variables within the graph. The most important consequence of this restriction is that it leads to the definition of a canonic form and a straightforward, linear time algorithm for its determination. In this paper, we extend Bryant's graphs to the representation of the spectra of Boolean functions. We show that Bryant's canonic form for function graphs readily extends to the spectral case. A number of algorithms for the manipulation of spectral graphs are developed including an algorithm for transforming between the Boolean and spectral graph representations. We show that a `sign' notation developed for our spectral graphs can be used to further reduce the size of Bryant's function graphs.
- Graph-Based Algorithms for Boolean Function Manipulation
- Boolean function representation and spectral characterization using AND/OR graphs
- scientific article; zbMATH DE number 910725
- scientific article; zbMATH DE number 512939
- On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783976)