Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We describe Haskell implementations of interesting combinatorial generationalgorithms with focus on boolean functions and logic circuit representations.First, a complete exact combinational logic circuit synthesizer is describedas a combination of catamorphisms and anamorphisms.Using pairing and unpairing functions on natural number representations oftruth tables, we derive an encoding for Binary Decision Diagrams BDDs withthe unique property that its boolean evaluation faithfully mimics itsstructural conversion to a a natural number through recursive application of amatching pairing function.We then use this result to derive ranking and unranking functions for BDDsand reduced BDDs.Finally, a generalization of the encoding techniques to Multi-Terminal BDDsis provided.The paper is organized as a self-contained literate Haskell program,available at this http URL .Keywords: exact combinational logic synthesis, binary decision diagrams,encodings of boolean functions, pairing-unpairing functions, ranking-unrankingfunctions for BDDs and MTBDDs, declarative combinatorics in Haskell



Autor: Paul Tarau

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados