On maximal QROBDD's of Boolean functions

作     者：Michon, JF Yunès, JB Valarcher, P 

作者机构：Univ Rouen LIFAR F-75821 Mont St Aignan France Univ Paris 07 LIAFA F-75013 Paris France 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2005年第39卷第4期

页      面：677-686页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Boolean functions Boolean complexity Boolean graphs binary decision diagrams BDD OBDD 

摘      要：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).