Article contents
On maximal QROBDD's of Boolean functions
Published online by Cambridge University Press: 15 October 2005
Abstract
We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 4 , October 2005 , pp. 677 - 686
- Copyright
- © EDP Sciences, 2005
References
- 1
- Cited by