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
      [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
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references