Issue Theoret. Informatics Appl. Volume 39, Number 4, October-December 2005 Page(s) 677 - 686 DOI 10.1051/ita:2005036

Theoret. Informatics Appl. 39, 677-686 (2005)
DOI: 10.1051/ita:2005036

On maximal QROBDD's of Boolean functions

Jean-Francis Michon¹, Jean-Baptiste Yunès² and Pierre Valarcher<sup>1

1</sup>  Université de Rouen, LIFAR, 75821 Mont Saint Aignan Cedex, France; jean.francis.michon@univ-rouen.fr; pierre.valarcher@univ-rouen.fr
²  Université Paris 7, LIAFA, 175 rue du Chevaleret, 75013 Paris, France; Jean-Baptiste.Yunes@liafa.jussieu.fr

(Received March, 2003. Accepted December, 2004.)

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).

Mathematics Subject Classification. 06E30, 68Q15, 94C10, 94C15

Key words: Boolean functions -- Boolean complexity -- Boolean graphs -- binary decision diagrams -- BDD -- OBDD


© EDP Sciences 2005

What is OpenURL?