Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog

Details Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog

2008-08-05

arxiv.org/abs/0808.0555v2

Computer Science

Logic in Computer Science

also in the informal proceedings of CICLOPS 2008 workshop at: http://clip.dia.fi.upm.es/Conferences/CICLOPS-2008/CICLOPS-2008-

Scientific paper

A "pairing function" J associates a unique natural number z to any two natural numbers x,y such that for two "unpairing functions" K and L, the equalities K(J(x,y))=x, L(J(x,y))=y and J(K(z),L(z))=z hold. Using pairing functions on natural number representations of truth tables, we derive an encoding for Binary Decision Diagrams 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 {\em ranking} and {\em unranking} functions for BDDs and reduced BDDs. The paper is organized as a self-contained literate Prolog program, available at http://logic.csci.unt.edu/tarau/research/2008/pBDD.zip Keywords: logic programming and computational mathematics, pairing/unpairing functions, encodings of boolean functions, binary decision diagrams, natural number representations of truth tables

Affiliated with

Also associated with

No associations

Rating

Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog 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 Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-549728