Geodesic
An inference algorithm for monotone Boolean functions associated with undirected graphs
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 9 (2016) no. 3, pp. 17-30 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Boolean functions are a modelling tool useful in many applications; monotone Boolean functions make up an important class of these functions. For instance, monotone Boolean functions can be used for describing the structure of the feasible subsystems of an infeasible system of constraints, because feasibility is a monotone feature. In this paper we consider monotone Boolean functions (MBFs), associated with undirected graphs, whose upper zeros are defined as binary tuples for which the corresponding subgraph of the original undirected graphs is either the empty graph, or it has no edges. For this class of MBFs, we present the settings of problems which are related to the search for upper zeros and maximal upper zeros of these functions. The notion of $k$-vertices and $(k, m)$-vertices in a graph is introduced. It is shown that for any $k$-vertices of the original graph there exists a maximal upper zero of an MBF associated with the graph, in which the component $x_{i}$ corresponding to this $k$-vertex takes the value $1$. Based on this statement, we construct an algorithm of searching for a maximal upper zero, for the class of MBFs under consideration, which allows one to find, under certain conditions, the solution to the problem of searching for a maximal upper zero, or to substantially reduce the dimension of the original problem. The proposed algorithm was extended for the case of $(k, m)$-vertices. This extended algorithm allows one to fix a bound on the deviation of an upper zero of the MBF from the maximal upper zeros, in the sense of the number of units in these tuples. The algorithm has the complexity $O(n^2p)$, where $n$ is a number of vertices and $p$ is a number of edges of the original graph.
Keywords: monotone Boolean function; upper zero of a monotone Boolean function; graph; algorithm of searching for maximal upper zeros of a monotone Boolean function. 
@article{VYURU_2016_9_3_a1,
     author = {D. N. Gainanov and V. A. Rasskazova},
     title = {An inference algorithm for monotone {Boolean} functions associated with undirected graphs},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {17--30},
     year = {2016},
     volume = {9},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2016_9_3_a1/}
}
TY  - JOUR
AU  - D. N. Gainanov
AU  - V. A. Rasskazova
TI  - An inference algorithm for monotone Boolean functions associated with undirected graphs
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2016
SP  - 17
EP  - 30
VL  - 9
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURU_2016_9_3_a1/
LA  - en
ID  - VYURU_2016_9_3_a1
ER  - 
%0 Journal Article
%A D. N. Gainanov
%A V. A. Rasskazova
%T An inference algorithm for monotone Boolean functions associated with undirected graphs
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2016
%P 17-30
%V 9
%N 3
%U http://geodesic.mathdoc.fr/item/VYURU_2016_9_3_a1/
%G en
%F VYURU_2016_9_3_a1
D. N. Gainanov; V. A. Rasskazova. An inference algorithm for monotone Boolean functions associated with undirected graphs. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 9 (2016) no. 3, pp. 17-30. http://geodesic.mathdoc.fr/item/VYURU_2016_9_3_a1/

[1] Gainanov D. N., Sombinatorial Geometry and Graphs in an Analysis of Infeasible Systems and Pattern Recognition, M., 2014 (in Russian)

[2] Gainanov D. N., “On One Criterion of the Optimality of an Algorithm for Evaluating Monotonic Boolean Functions”, USSR Computational Mathematics and Mathematical Physics, 24:4 (1984), 176–181 | DOI | MR

[3] Korshunov A. D., “Monotone Boolean functions”, Progress in Mathematical Sciences, 58:5(535) (2003), 89–162 (in Russian) | MR | Zbl

[4] Sapozhenko A. A., Dedekind's Problem and the Method of Boundary Functionals, M., 2009 (in Russian)

[5] Bioch J. C., Ibaraki T., Makino K., “Minimum Self-Dualdecompositions of Positive Dual-Minor Boolean Functions”, Discrete Applied Mathematics, 96–97 (1999), 307–326 | DOI | MR | Zbl

[6] Boros E., Hammer P., Ibaraki T., Kawakami K., “Polynomial Time Ecognition of 2-monotonic Positive Boolean Functions Given by an Oracle”, SIAM Journal on Computing, 26 (1997), 93–109 | DOI | MR | Zbl

[7] Domingo C., Mishra N., Pitt L., “Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries”, Machine Learning, 37:1 (1999), 89–110 | DOI | Zbl

[8] Makino K., Ibaraki T., “A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions”, Journal of Algorithms, 26:2 (1998), 291–305 | DOI | MR | Zbl

[9] Makino K., Ibaraki T., “The Maximum Latency and Identification of Positive Boolean Functions”, SIAM Journal on Computing, 26 (1997), 1363–1383 | DOI | MR | Zbl

[10] Torvik V. I., Triantaphyllou E., “Guided Inference of Nested Monotone Boolean Functions”, Information Sciences, 151, suppl. (2003), 171–200 | DOI | MR | Zbl

[11] Triantaphyllou E., Data Mining and Knowleadge Discovery Via Logic-Based Methods. Theory, Algorithms and Applications, Springer, N.Y., 2010 | MR

[12] Valiant L., “A Theory of the Learnable”, Communications of the ACM, 27:11 (1984), 1134–1142 | DOI | Zbl

[13] Torvik V. I., Triantaphyllou E., “Inference of Monotone Boolean Functions”, Encyclopedia of Optimization, Springer, N. Y., 2009, 1591–1598 | DOI