Abstract <p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Resolving Sets for Monotone Boolean Function Subclasses

  • Hasmik Sahakyan,
  • Levon Aslanyan

摘要

Abstract

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.