Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell - Computer Science > Data Structures and AlgorithmsReport as inadecuate




Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

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



Author: Paul Tarau

Source: https://arxiv.org/







Related documents