Counting inequivalent monotone Boolean functions.

DOI10.1016/J.DAM.2013.11.015MaRDI QIDQ2440095zbMATH OpenOpenAlexFDO

Authors Tamon Stephen, Timothy Yusun

Publication date 27 March 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.4623

zbMATH Keywords

Dedekind numbersisotone Boolean functionsmonotone Boolean functionsnumbers of Boolean functions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Boolean functions (06E30)

Abstract: Monotone Boolean functions (MBFs) are Boolean functions $f:{0,1}^{n}ightarrow0,1$ satisfying the monotonicity condition $xleqyRightarrowf(x)leqf(y)$ for any $x,yin{0,1}^n$. The number of MBFs in n variables is known as the $n$th 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 inequivalent if one can be obtained from the other by renaming 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 MBF's 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.

Recommendations

• Algorithms counting monotone Boolean functions
• scientific article; zbMATH DE number 3867232
• The number of monotone and self-dual Boolean functions.
• scientific article; zbMATH DE number 1839468
• On the distribution of the number of monotone Boolean functions relative to the number of lower units

Cites work

• A computation of the eighth Dedekind number
• A solution of Dedekind's problem on the number of isotone Boolean functions.
• Algorithms counting monotone Boolean functions
• Counting inequivalent monotone Boolean functions.
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3552560 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 3366941 (Why is no real title available?)
• Monotone Boolean functions
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On the complexity of the decisive problem in simple and weighted games
• Semi-distance codes and Steiner systems

Cited in

(16)

• Algorithms counting monotone Boolean functions
• Enumerating and categorizing positive Boolean functions separable by a \(k\)-additive capacity
• The monoid of monotone functions on a poset and quasi-arithmetic multiplicities for uniform matroids
• Maximal sensitivity of Boolean nested canalizing functions
• Counting inequivalent monotone Boolean functions.
• On the expressivity of inconsistency measures
• The number of monotone and self-dual Boolean functions.
• On the number of bipolar Boolean functions
• scientific article; zbMATH DE number 1839468 (Why is no real title available?)
• scientific article; zbMATH DE number 7596570 (Why is no real title available?)
• scientific article; zbMATH DE number 7640036 (Why is no real title available?)
• scientific article; zbMATH DE number 7286679 (Why is no real title available?)
• On the enumeration of some inequivalent monotone Boolean functions
• Solving systems of equations on antichains for the computation of the ninth Dedekind number
• Counting unate and monotone Boolean functions under restrictions of balancedness and non-degeneracy
• Computation of immediate neighbours of monotone Boolean functions

Describes a project that uses

Uses Software

• Matlab
• JBool
• OEIS

This page was built for publication: Counting inequivalent monotone Boolean functions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440095)