Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog

Simple item page
dc.creatorTarau, Paul
dc.date2008-08-05
dc.date2009-02-04
dc.date.accessioned2026-07-07T12:37:09Z
dc.date.available2026-07-07T12:37:09Z
dc.descriptionA "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
dc.descriptionalso in the informal proceedings of CICLOPS 2008 workshop at: http://clip.dia.fi.upm.es/Conferences/CICLOPS-2008/CICLOPS-2008-proceedings.pdf
dc.identifierhttps://arxiv.org/abs/0808.0555
dc.identifierhttp://arxiv.org/abs/0808.0555
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218341
dc.subjectLogic in Computer Science
dc.subjectSymbolic Computation
dc.titlePairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog
dc.typetext

Files

Collections

arXiv