Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell

Details Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell

2008-08-06

arxiv.org/abs/0808.0760v1

Computer Science

Data Structures and Algorithms

unpublished draft

Scientific paper

We describe Haskell implementations of interesting combinatorial generation algorithms with focus on boolean functions and logic circuit representations. First, a complete exact combinational logic circuit synthesizer is described as a combination of catamorphisms and anamorphisms. Using pairing and unpairing functions on natural number representations of truth tables, we derive an encoding for Binary Decision Diagrams (BDDs) with the unique property that its boolean evaluation faithfully mimics its structural conversion to a a natural number through recursive application of a matching pairing function. We then use this result to derive ranking and unranking functions for BDDs and reduced BDDs. Finally, a generalization of the encoding techniques to Multi-Terminal BDDs is provided. The paper is organized as a self-contained literate Haskell program, available at http://logic.csci.unt.edu/tarau/research/2008/fBDD.zip . Keywords: exact combinational logic synthesis, binary decision diagrams, encodings of boolean functions, pairing/unpairing functions, ranking/unranking functions for BDDs and MTBDDs, declarative combinatorics in Haskell

Affiliated with

Also associated with

No associations

Rating

Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-27467