Diagramme de Décision Fonctionnel Ordonné: Une Sémantique Fonctionnelle pour les Diagrammes de Décision Binaires

Autor: Thibault, Joan, Ghorbal, Khalil
Přispěvatelé: Modélisation hybride & conception par contrats pour les systèmes embarqués multi-physiques (HYCOMES), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Inria, INRIA Rennes, Institut National de Recherche en Informatique et en Automatique (Inria), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: [Research Report] RR-9333, Inria. 2020
Popis: Several BDD variants were designed to exploit special features of Boolean functions to achieve better compression rates.Deciding a priori which variant to use is as hard as constructing the diagrams themselves and the conversion between variants comes in general with a prohibitive cost.This observation leads naturally to a growing interest into when and how one can combine existing variants to benefit from their respective sweet spots.In this paper, we introduce a novel framework, termed \lambdaDD (LDD), that revisits BDD from a purely functional point of view.The framework allows to classify the already existing variants, including the most recent ones like ChainDD and ESRBDD, as implementations of a special class of ordered models.We enumerate, in a principled way, all the models of this class and isolate its most expressive model.This new model, termed \lambdaDD-O-NUCX, is suitable for both dense and sparse Boolean functions, and, unlike ChainDD and ESRBDD, is invariant by negation.The canonicity of \lambdaDD-O-NUCX is formally verified using the Coq proof assistant.We furthermore provide experimental evidence corroborating our theoretical findings: more expressive \lambdaDD models achieve, indeed, better memory compression rates.; Les Diagrammes de Décision Binaires (BDD) sont une structure qui a été décliné en de nombreux variants, chacun conçu pour exploiter au mieux une propriété particulière des fonctions Booléennes et ainsi réduire leur taille mémoire.Cependant, décider quel variant est le plus adapté à priori est aussi difficile que construire chaque représentation.De plus la conversion entre les variants coûte également trop chère pour être utilisable en pratique.Ces observations ont conduit naturellement à un intérêt grandissant pour combiner des variants pour tirer parti de leurs avantages respectifs.Cet article introduit un cadre théorique à cette problématique en introduisant une méta-structure nommée \lambdaDD qui adopte un point de vue purementfonctionnel sur les BDD.Les diagrammes \lambdaDD permettent d'abstraire les variants classiques (par exemple ROBDD et ZDD) ainsi que des variants récents (en particulier ChainDD et ESRBDD)comme des modèles d'une classe de modèles ordonnés que nous appelons \lambdaDD-ODans ces modèles ordonnés, les variables sont évaluées en suivant un ordre global strict.Nous énumérons les éléments de cette classe et isolons son modèle le plus expressif que nous nommons \lambdaDD-O-NUCX.Ce modèle permet non seulement de capturer les variables canalisantes (ce qui le rend plus expressif que ESRBDD par exemple) mais exploiteaussi une propriété supplémentaire: les xor-variables.Le modèle est également invariant par négation, ce qui permet de calculer la négation d'une fonction Booléenne en temps constant.La canonicité de \lambdaDD-O-NUCX est formellement vérifiée en utilisant l'assistant de preuve Coq.De plus, nous fournissons des résultats expérimentaux confirmant l'intérêt de \lambdaDD-O-NUCX.
Databáze: OpenAIRE
Externí odkaz: