| Issue |
RAIRO-Theor. Inf. Appl.
Volume 39, Number 4, October-December 2005
|
|
|---|---|---|
| Page(s) | 677 - 686 | |
| DOI | https://doi.org/10.1051/ita:2005036 | |
| Published online | 15 October 2005 | |
On maximal QROBDD's of Boolean functions
1
Université de Rouen, LIFAR, 75821 Mont Saint Aignan Cedex, France; jean.francis.michon@univ-rouen.fr; pierre.valarcher@univ-rouen.fr
2
Université Paris 7, LIAFA, 175 rue du Chevaleret, 75013 Paris, France; Jean-Baptiste.Yunes@liafa.jussieu.fr
Received:
March
2003
Accepted:
December
2004
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).
Mathematics Subject Classification: 06E30 / 68Q15 / 94C10 / 94C15
Key words: Boolean functions / Boolean complexity / Boolean graphs / binary decision diagrams / BDD / OBDD
© EDP Sciences, 2005
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.