ﻻ يوجد ملخص باللغة العربية
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
In this paper an algorithm is designed which generates in-equivalent Boolean functions of any number of variables from the four Boolean functions of single variable. The grammar for such set of Boolean function is provided. The Turing Machine that accepts such set is constructed.
We present an algorithm to compute exact literal-weighted model counts of Boolean formulas in Conjunctive Normal Form. Our algorithm employs dynamic programming and uses Algebraic Decision Diagrams as the primary data structure. We implement this tec
Classification of Non-linear Boolean functions is a long-standing problem in the area of theoretical computer science. In this paper, effort has been made to achieve a systematic classification of all n-variable Boolean functions, where only one affi
We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Let f be a Boolean function with Fourier suppor
The differential-reduction algorithm, which allows one to express generalized hypergeometric functions with parameters of arbitrary values in terms of such functions with parameters whose values differ from the original ones by integers, is discussed