Name
Abstract | ||
|---|---|---|
Monotone Boolean functions (MBFs) are Boolean functions f:{0,1}^n-{0,1} satisfying the monotonicity condition x@?y@?f(x)@?f(y) for any x,y@?{0,1}^n. The number of MBFs in n variables is known as the nth Dedekind number. It is a longstanding computational challenge to determine these numbers exactly: these values are only known for n at most 8. Two monotone Boolean functions are equivalent if one can be obtained from the other by permuting the variables. The number of inequivalent MBFs in n variables was known only for up to n=6. In this paper we propose a strategy to count inequivalent MBFs by breaking the calculation into parts based on the profiles of these functions. As a result we are able to compute the number of inequivalent MBFs in 7 variables. The number obtained is 490013148. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2013.11.015 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
longstanding computational challenge,nth dedekind number,monotone boolean function,inequivalent mbfs,inequivalent monotone boolean function,monotonicity condition,boolean function,n variable | Journal | 167 |
ISSN | Citations | PageRank |
0166-218X | 5 | 0.54 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tamon Stephen | 1 | 121 | 16.03 |
| Timothy Yusun | 2 | 6 | 1.24 |