Average Degree in the Interval Graph of a Random Boolean Function
Keywords:
Random Boolean function, interval graphAbstract
We consider an n-ary random Boolean function f such that for and study its geometric model, the so called interval graph. The interval graph of a Boolean function was introduced by Sapozhenko and has been used in construction of schemes realizing Boolean functions. Using this model, we estimate the number of maximal intervals intersecting a given maximal interval of a random Boolean function and prove that the asymptotic bound on the logarithm of the number is , where ?(n) ? 0 as .Downloads
Download data is not yet available.
Downloads
Published
2012-01-26
How to Cite
Toman, E., Olejár, D., & Stanek, M. (2012). Average Degree in the Interval Graph of a Random Boolean Function. Computing and Informatics, 27(4), 627–638. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/235
Issue
Section
Articles