The problem of counting all inequivalent monotone boolean functions of nine variables is considered. We solve the problem using known algorithms and deriving new ones when necessary. We describe methods to count fixed...
详细信息
The problem of counting all inequivalent monotone boolean functions of nine variables is considered. We solve the problem using known algorithms and deriving new ones when necessary. We describe methods to count fixed points in sets of all monotone boolean functions under a given permutation of input variables. With these techniques as a basis, we tabulate the cardinalities of these sets for nine variables. By applying Burnside's lemma and the numbers obtained, we calculate the number of inequivalent monotone boolean functions of 9 variables, which equals 789,204,635,842,035,040,527,740,846,300,252,680.
A boolean function f : {0, 1}(n) bar right arrow {0, 1} is a monotoneboolean function (MBF) of n variables if for each pair of vectors x, y is an element of {0, 1}(n) from x <= y follows f (x) <= f (y). Two MBF...
详细信息
A boolean function f : {0, 1}(n) bar right arrow {0, 1} is a monotoneboolean function (MBF) of n variables if for each pair of vectors x, y is an element of {0, 1}(n) from x <= y follows f (x) <= f (y). Two MBFs are considered equivalent if one of them can be obtained from the other by permuting the input variables. Let d(n) be the number of MBFs of n variables (which is known as Dedekind number) and let r(n) be a number of non-equivalent MBFs of n variables. The numbers d(n) and r(n) have been so far calculated for n <= 8, and n <= 7, respectively. This paper presents the calculation of r(8) = 1392195548889993358. Determining Dedekind numbers and r(n) is a long-standing problem.
The study of monotone boolean functions (MBFs) has a long history. We explore a connection between MBFs and ordinary differential equation (ODE) models of gene regulation, and, in particular, a problem of the realizat...
详细信息
The study of monotone boolean functions (MBFs) has a long history. We explore a connection between MBFs and ordinary differential equation (ODE) models of gene regulation, and, in particular, a problem of the realization of an MBF as a function describing the state transition graph of an ODE. We formulate a problem of joint realizability of finite collections of MBFs by establishing a connection between the parameterized dynamics of a class of ODEs and a collection of MBFs. We pose a question of what collections of MBFs can be realized by ODEs that belong to nested classes defined by increased algebraic complexity of their right-hand sides. As we progressively restrict the algebraic form of the ODE, we show by a combination of theory and explicit examples that the class of jointly realizable functions strictly decreases. Our results impact the study of regulatory network dynamics, as well as the classical area of MBFs. We conclude with a series of potential extensions and conjectures. (C) 2022 Elsevier B.V. All rights reserved.
The average-case complexity of computing monotone boolean functions by straight-line programs without memory with a conditional stop in the basis of all booleanfunctions of at most two variables is considered. For th...
详细信息
The average-case complexity of computing monotone boolean functions by straight-line programs without memory with a conditional stop in the basis of all booleanfunctions of at most two variables is considered. For the set of all monotone boolean functions of n variables, Shannon-type upper and lower bounds for the average-case complexity are established for n -> infinity.
We consider average-case complexity of computing monotone boolean functions by straight-line programs with a conditional stop over the basis of all booleanfunctions of at most two variables. For the set of all n-ary ...
详细信息
We consider average-case complexity of computing monotone boolean functions by straight-line programs with a conditional stop over the basis of all booleanfunctions of at most two variables. For the set of all n-ary monotone boolean functions new Shannon-type upper and lower bounds for the average-case complexity n -> infinity are established.
One of the problems of modern discrete mathematics is Dedekind's problem on the number of monotone boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had ...
详细信息
One of the problems of modern discrete mathematics is Dedekind's problem on the number of monotone boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone boolean functions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of booleanfunctions of intersection MS of two classes-the class of monotonefunctions and the class of self-dual functions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the majority voting function of an odd number of variables is monotone and self-dual. The majority voting function of an even number of variables is determined. Free voting functions, which are functions with fictitious variables similar in properties to majority voting functions, are introduced. Then the union of a set of majority voting functions and a set of free voting functions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for vertical bar MS vertical bar. For the class MS of monotone self-dual functions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for vertical bar MS vertical bar is presented for the first time.
monotone boolean functions (MBFs) are booleanfunctions f : {0, 1}(n) -> {0, 1} satisfying the monotonicity condition x <= y double right arrow f(x) <= f(y) for any x, y is an element of {0,1}(n)(.) The numbe...
详细信息
monotone boolean functions (MBFs) are booleanfunctions f : {0, 1}(n) -> {0, 1} satisfying the monotonicity condition x <= y double right arrow f(x) <= f(y) for any x, y is an element of {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. (C) 2013 Elsevier B.V. All rights reserved.
There are significant difficulties for the acceptance of black-box Machine Learning (ML) models by subject matter experts (SMEs) despite significant achievements of many blackbox models. A promising way to address thi...
详细信息
ISBN:
(纸本)9798350380170;9798350380163
There are significant difficulties for the acceptance of black-box Machine Learning (ML) models by subject matter experts (SMEs) despite significant achievements of many blackbox models. A promising way to address this problem is by building a trustable, qualitative, interpretable models for the task based on SME knowledge. Such qualitative models can work as qualitative explainers of black-box models or as sanity checks for them. In this paper, qualitative models operate with ordinal attributes, which can be boolean or k-valued attributes with a small k. Humans easier understand and reason with such attributes that with continuous numeric attributes with many more values. Some ML tasks do not have sufficient training data. Building qualitative models with a SME ("expert models") is a way to solve these tasks solely with a SME's knowledge. The proposed monotone Ordinal Expert Knowledge Acquisition (MOEKA) system allows building "expert models" through interview phases with the SME. Monotonicity is a key property of the system that is tested and used to shorten the interview process with a SME along with new methods for selecting the order of questions. MOEKA rather directly approximates domain knowledge in contrast with other ML explainers, which approximate black-box ML models. MOEKA can be also used as a method of database searching. Several case studies on gout, diabetes, and housing demonstrate efficiency of MOEKA.
In this paper, we present the empirical results for relationships between time (depth) and space (number of nodes) complexity of decision trees computing monotone boolean functions, with at most five variables. We use...
详细信息
In this paper, we present the empirical results for relationships between time (depth) and space (number of nodes) complexity of decision trees computing monotone boolean functions, with at most five variables. We use Dagger (a tool for optimization of decision trees and decision rules) to conduct experiments. We show that, for each monotoneboolean function with at most five variables, there exists a totally optimal decision tree which is optimal with respect to both depth and number of nodes.
We consider two types of models of regulatory network dynamics: boolean maps and systems of switching ordinary differential equations. Our goal is to construct all models in each category that are compatible with the ...
详细信息
We consider two types of models of regulatory network dynamics: boolean maps and systems of switching ordinary differential equations. Our goal is to construct all models in each category that are compatible with the directed signed graph that describe the network interactions. This leads to consideration of lattice of monotone boolean functions (MBF), poset of non-degenerate MBFs, and a lattice of chains in these sets. We describe explicit inductive construction of these posets where the induction is on the number of inputs in MBF. Our results allow enumeration of potential dynamic behavior of the network for both model types, subject to practical limitation imposed by the size of the lattice of MBFs described by the Dedekind number.
暂无评论