.png){kind=icon}
.png){kind=icon}
Return
Resolving Sets for Monotone Boolean Function Subclasses
.png){kind=icon}
PRE
AI
DOI：10.1134/S1054661825701366.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the set of all Boolean functions, the class of monotone Boolean functions is of significant importance. Many discrete extremal problems can be formulated and solved in terms of monotone Boolean functions. Monotone Boolean recognition refers to the problem of recovering an unknown monotone Boolean function using a restricted set of observations provided through oracle queries, with the objective of minimizing the total number of queries required. This reconstruction problem is central to several domains, including combinatorial optimization, information theory, and machine learning, where it enables the identification of hidden monotonic structures. The full class of monotone Boolean functions is complex, and several important subclasses have been identified and studied. Among them is a class in which the units correspond to initial segments of the lexicographic order on layers of the binary cube, and consequently, the zeros correspond to initial segments of the reverse-lexicographic order. In this paper, we introduce an extension that allows a single unit (or a single zero) to appear at a prescribed position within the initial segment of the lexicographic (or reverse-lexicographic) ordering of the layers corresponding to the function's zeros (or units). We determine a deadlock-resolving set for this extended class, and provide estimates of its cardinality.
Keywords:
monotone Boolean function
resolving sets
query-based recognition
Journal
P
IF:
0.5
Papers:
22
Citations:
566