No label defined (Q3783976)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4047617
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4047617 |
Statements
1987
0 references
rooted directed acyclic graph
0 references
spectra of Boolean functions
0 references
function graphs
0 references
spectral graph representations
0 references
0.8477600812911987
0 references
0.8072550296783447
0 references
[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.
0 references