RAIRO - Theoretical Informatics and Applications

Table of Contents - October 2005 - Volume 39, Issue 04  

Research Article

On maximal QROBDD's of Boolean functions

Michon, Jean-Francisa1, Yunès, Jean-Baptistea2 and Valarcher, Pierrea1

a1 Université de Rouen, LIFAR, 75821 Mont Saint Aignan Cedex, France; jean.francis.michon@univ-rouen.fr; pierre.valarcher@univ-rouen.fr

a2 Université Paris 7, LIAFA, 175 rue du Chevaleret, 75013 Paris, France; Jean-Baptiste.Yunes@liafa.jussieu.fr

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

(Received March 2003)

(Accepted December 2004)

(Online publication October 15 2005)

Key Words:

  • Boolean functions;
  • Boolean complexity;
  • Boolean graphs;
  • binary decision diagrams;
  • BDD;
  • OBDD

Mathematics Subject Classification:

  • 06E30;
  • 68Q15;
  • 94C10;
  • 94C15