On maximal QROBDD's of Boolean functions
Université de Rouen, LIFAR, 75821 Mont Saint Aignan Cedex, France; firstname.lastname@example.org; email@example.com
2 Université Paris 7, LIAFA, 175 rue du Chevaleret, 75013 Paris, France; Jean-Baptiste.Yunes@liafa.jussieu.fr
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