43 
 

Mathematical Problems of Computer Science 52, 43--53, 2019. 

 
 

UDC 519.7 
 

Notes on Monotone Recognition in Multi-Valued Grids 
 

Levon H. Aslanyan and Hasmik A. Sahakyan 
 

Institute for Informatics and Automation Problems of NAS RA 
e-mail: lasl@sci.am,  hsahakyan@sci.am 

 
Abstract 

 
 

A novel method of monotone recognition based on the partitioning of the grid 
into discrete structures isomorphic to binary cubes (called “cube-split” 
technique) was proposed in our recent work, and a theoretical level description 
of two algorithms /algorithmic schemes/ solving this problem was also 
introduced. This paper provides implementation details of those algorithms, as 
well as focuses on the recognition of monotone binary functions with a small 
number of units. 

Keywords: Monotone function recognition, multi-valued grid, cube-splitting. 
 
 
 

1. Introduction 
 
Let 𝛯𝛯𝑚𝑚+1

𝑛𝑛  denote the 𝑛𝑛-th Cartesian degree of the set 𝛯𝛯𝑚𝑚+1 = {0,1, ⋯ , 𝑚𝑚}:  
𝛯𝛯𝑚𝑚+1
𝑛𝑛 = {(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛)|𝑎𝑎𝑖𝑖 ∈ 𝛯𝛯𝑚𝑚+1, 𝑖𝑖 = 1, ⋯ , 𝑛𝑛}, 

or, in other words, 𝛯𝛯𝑚𝑚+1
𝑛𝑛  is the set of vertices of the 𝑛𝑛-dimensional (𝑚𝑚 + 1)-valued discrete grid. 

The total number of vertices of 𝛯𝛯𝑚𝑚+1
𝑛𝑛  is equal to (𝑚𝑚 + 1)𝑛𝑛. We consider a component-wise 

partial order “≤” on 𝛯𝛯𝑚𝑚+1
𝑛𝑛  defined in the following way: for arbitrary vertices 𝑎𝑎 = (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) 

and 𝑏𝑏 = (𝑏𝑏1, ⋯ , 𝑏𝑏𝑛𝑛) of 𝛯𝛯𝑚𝑚+1
𝑛𝑛 , 𝑎𝑎 precedes 𝑏𝑏 (𝑎𝑎 ≤ 𝑏𝑏) if and only if 𝑎𝑎𝑖𝑖 ≤ 𝑏𝑏𝑖𝑖 for 𝑖𝑖 = 1, ⋯ , 𝑛𝑛. Then, 

(𝛯𝛯𝑚𝑚+1
𝑛𝑛 , ≤) is a partially ordered set; we will use its Hasse diagram for geometrical 

interpretations.    
𝑓𝑓(𝑥𝑥1, 𝑥𝑥2, ⋯ , 𝑥𝑥𝑛𝑛): 𝛯𝛯𝑚𝑚+1

𝑛𝑛 → {0,1} is called a binary function defined on 𝛯𝛯𝑚𝑚+1
𝑛𝑛 . We say that 

𝑓𝑓(𝑥𝑥1, 𝑥𝑥2, ⋯ , 𝑥𝑥𝑛𝑛) is a monotone function if for any two vertices 𝑎𝑎, 𝑏𝑏 of 𝛯𝛯𝑚𝑚+1
𝑛𝑛 ,  𝑎𝑎 ≥ 𝑏𝑏 implies: 

𝑓𝑓(𝑎𝑎) ≥ 𝑓𝑓(𝑏𝑏). The vertices of 𝛯𝛯𝑚𝑚+1
𝑛𝑛 , where 𝑓𝑓 takes the value “1”, are called units of the function. 

The set of units of 𝑓𝑓 is usually denoted by 𝑁𝑁𝑓𝑓. The vertices of 𝛯𝛯𝑚𝑚+1
𝑛𝑛 , where 𝑓𝑓 takes the value “0” 

are called zeros of the function. 𝑎𝑎1 ∈ 𝛯𝛯𝑚𝑚+1
𝑛𝑛  is called a lower unit of 𝑓𝑓, if 𝑓𝑓(𝑎𝑎1) = 1 and 𝑓𝑓(𝑏𝑏) =

0 for every 𝑏𝑏 ∈ 𝛯𝛯𝑚𝑚+1
𝑛𝑛  less than 𝑎𝑎1. 𝑎𝑎0 ∈ 𝛯𝛯𝑚𝑚+1

𝑛𝑛  is called an upper zero of 𝑓𝑓, if 𝑓𝑓(𝑎𝑎0) = 0 and 
𝑓𝑓(𝑏𝑏) = 1 for every 𝑏𝑏 ∈ 𝛯𝛯𝑚𝑚+1

𝑛𝑛  greater than 𝑎𝑎0.  

mailto:lasl@sci.am
mailto:hsahakyan@sci.am


Notes on Monotone Recognition in-Multi-Valued Grids 
 

44 

Fig. 1 demonstrates the Hasse diagram of 𝛯𝛯5
3, and a monotone binary function 𝑓𝑓 defined 

on 𝛯𝛯5
3. Highlighted vertices (4,4,4), (4,4,3), (4,3,4), (3,4,4), (4,4,2), (4,3,3), (3,4,3), (3,3,4), 

(2,4,4), (4,3,2), (3,3,3), (2,4,3), (1,4,4), (1,4,3) are units of the function, where (4,3,2), (3,3,3), 
and (1,4,3) are its lower units. The rest of vertices of 𝛯𝛯5

3 are zeros of the function, and (4,4,1), 
(4,2,4), (3,4,2),(2,3,4), and (0,4,4) are its upper zeros. 

We consider the problem of query-based algorithmic identification/recognition of 
monotone binary functions defined on 𝛯𝛯𝑚𝑚+1

𝑛𝑛 . This problem is initially investigated by V. 
Korobkov and V. Alekseev, but also, consecutively, by many other authors [1-4]. For 𝑚𝑚 = 1, 
this is the case of ordinary monotone Boolean functions defined on the binary cube 𝐸𝐸𝑛𝑛, 𝐸𝐸𝑛𝑛 =
{(𝛼𝛼1, ⋯ , 𝛼𝛼𝑛𝑛)|𝛼𝛼𝑖𝑖 ∈ {0,1}, 𝑖𝑖 = 1, ⋯ , 𝑛𝑛}. Hansel’s chain-splitting technique of 𝐸𝐸𝑛𝑛 [5] is a well-
known effective tool for monotone Boolean function recognition. The outline of the algorithm is 
as follows: the set of vertices of the binary cube is partitioned into disjoint chains of different 
lengths (there are a total of 𝐶𝐶𝑛𝑛

⌊𝑛𝑛/2⌋ chains in the 𝑛𝑛-dimensional cube). A key property of the 
Hansel’s chains is that once the function values are known for all the vertices in all the chains of 
length 𝑘𝑘, then the function values, inferable by monotonicity, are unknown for at most two 
vertices in each chain of the next length 𝑘𝑘 + 2. The maximum number of queries to recognize 
the monotone Boolean function defined on the 𝑛𝑛-dimensional cube is 𝐶𝐶𝑛𝑛

⌊𝑛𝑛/2⌋+𝐶𝐶𝑛𝑛
⌊𝑛𝑛/2⌋+1.  

 

 
 

Fig. 1. Monotone function defined on 𝛯𝛯5
3. 

 
 
An extension of this technique to the case of multi-valued grids and monotone binary 

functions is obtained in [2-3]. In [2], V. Alekseev developed the algorithm 𝑈𝑈0 for recognition of 
a monotone binary function defined on 𝛯𝛯𝑘𝑘1𝑘𝑘2⋯𝑘𝑘𝑛𝑛 = 𝛯𝛯𝑘𝑘1 × 𝛯𝛯𝑘𝑘2 × ⋯ × 𝛯𝛯𝑘𝑘𝑛𝑛, (𝛯𝛯𝑘𝑘𝑖𝑖 = {0,1, ⋯ , 𝑘𝑘 −
1}, 𝑖𝑖 = 1, ⋯ , 𝑛𝑛), which, in some sense, tries to generalize G.Hansel’s algorithm. [2] proved that: 

 
𝑇𝑇(𝑈𝑈0)
𝑇𝑇(𝑈𝑈𝑜𝑜𝑜𝑜𝑜𝑜)

≤ 1
2
⌈𝑙𝑙𝑙𝑙𝑙𝑙2(𝑘𝑘 − 1)⌉, 

 

444

443 434 344

442 433 424 343 334 244

432 423 342 324 243 234333

422 332 323 242 233 224

322 232 223

222

144

044134143314404413341431440

441 414

430 431 340 412 331 403 241 313 304 142 214 133 124 043 034

024033114042123204132213141303231312240321402330411420

410

400

401 320 311 230 302 221 140 212 131 203 122 041 113 032 104 023 014

004013022103031112040121202130211220301310

300 210 201 120 111 030 102 021 012 003

002011020101110200

100 010 001

000



L. Aslanyan and  H. Sahakyan 
 

45 

Where 𝑇𝑇(𝑈𝑈0) denotes the complexity of 𝑈𝑈0, and 𝑇𝑇(𝑈𝑈𝑜𝑜𝑜𝑜𝑜𝑜) is the complexity of the optimal 
algorithm 𝑈𝑈𝑜𝑜𝑜𝑜𝑜𝑜, 𝑘𝑘 = 𝑚𝑚𝑎𝑎𝑥𝑥𝑘𝑘𝑖𝑖. It is also found that:  
 

𝑇𝑇(𝑈𝑈𝑜𝑜𝑜𝑜𝑜𝑜) ≥ |𝑀𝑀| + |𝑁𝑁| and 𝑇𝑇(𝑈𝑈0) ≤ |𝑀𝑀| + ⌊𝑙𝑙𝑙𝑙𝑙𝑙2𝑘𝑘⌋ ∙ |𝑁𝑁|,  
 

where 𝑀𝑀 and 𝑁𝑁 are the 2 sets of vertices in the middle layer area of 𝛯𝛯𝑘𝑘1𝑘𝑘2⋯𝑘𝑘𝑛𝑛: 
 

𝑀𝑀 = �(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) ∈ 𝛯𝛯𝑘𝑘1𝑘𝑘2⋯𝑘𝑘𝑛𝑛 ∶  𝑎𝑎1 + ⋯ + 𝑎𝑎𝑛𝑛 = �
1
2
∑ (𝑘𝑘𝑖𝑖 − 1)
𝑛𝑛
𝑖𝑖=1 ��,  

𝑁𝑁 = �(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) ∈ 𝛯𝛯𝑘𝑘1𝑘𝑘2⋯𝑘𝑘𝑛𝑛  ∶  𝑎𝑎1 + ⋯ + 𝑎𝑎𝑛𝑛 = �
1
2
∑ (𝑘𝑘𝑖𝑖 − 1)
𝑛𝑛
𝑖𝑖=1 � + 1�. 

 
In case of 𝛯𝛯𝑚𝑚+1

𝑛𝑛 the sets in the two middle layers are:  
 

𝑀𝑀0 = �(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) ∈ 𝛯𝛯𝑚𝑚+1
𝑛𝑛 ∶  𝑎𝑎1 + ⋯ + 𝑎𝑎𝑛𝑛 = �

𝑚𝑚∙𝑛𝑛
2
��,  

𝑁𝑁0 = �(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) ∈ 𝛯𝛯𝑚𝑚+1
𝑛𝑛 ∶  𝑎𝑎1 + ⋯ + 𝑎𝑎𝑛𝑛 = �

𝑚𝑚∙𝑛𝑛
2
� + 1�, 

 
and consequently, the estimate of complexity of the algorithm 𝑈𝑈0 on 𝛯𝛯𝑚𝑚+1

𝑛𝑛 will be:  
 

𝑇𝑇(𝑈𝑈0) ≤ |𝑀𝑀0| + ⌊𝑙𝑙𝑙𝑙𝑙𝑙2𝑚𝑚⌋ ∙ |𝑁𝑁0|. 
 
A recent novel method of the monotone recognition based on a partitioning of the grid 

into discrete structures isomorphic to binary cubes (called “cube-split” technique) is proposed in 
[6], and two algorithms /algorithmic schemes/ solving this problem are also introduced. This 
paper provides implementation details of these algorithms, as well as focuses on the recognition 
of monotone binary functions with a small number of units.  

The paper is organized as follows: Section 2 introduces the cube-splitting technique. 
Section 3 provides the implementation framework of these algorithmic schemes. Section 4 
addresses some particular cases with a small number of units that comes from applications.  

 

2. The Cube-Splitting Technique 
 
In this section we introduce the cube-splitting technique of recognition of monotone binary 
functions [6]. Two homogeneous areas inside the 𝛯𝛯𝑚𝑚+1

𝑛𝑛  are defined in the following way: 
- upper homogeneous area  𝐻𝐻�, - this is the set of all “upper” elements of 𝛯𝛯𝑚𝑚+1𝑛𝑛 , i.e., 

elements with all-coordinate values ≥ 𝑚𝑚/2; 
- lower homogeneous area 𝐻𝐻�, – this is the set of all “lower” elements, i.e., elements with 

all-coordinate values ≤ 𝑚𝑚/2. It is clear that: 
 

�𝐻𝐻�� = �𝐻𝐻�� = �
(m+1

2
)nfor odd 𝑚𝑚,

(𝑚𝑚
2

+ 1)𝑛𝑛 for even 𝑚𝑚
. 

 
The following results were introduced in [6]. 
 

(1) 𝛯𝛯𝑚𝑚+1𝑛𝑛  can be split into �𝐻𝐻�� disjoint discrete structures isomorphic to binary cubes:  
 



Notes on Monotone Recognition in-Multi-Valued Grids 
 

46 

𝛯𝛯𝑚𝑚+1
𝑛𝑛 = ℰ1 ∪ ⋯∪ ℰ|𝐻𝐻�|, 

 
where every ℰ𝑖𝑖 contains exactly one vertex from 𝐻𝐻�, while the remaining vertices of ℰ𝑖𝑖 can be 
determined uniquely by this vertex through the complementarity interchanges of the 
coordinate values. ℰ𝑖𝑖 ∩ ℰ𝑗𝑗 = ∅, if 𝑖𝑖 ≠ 𝑗𝑗. The procedure is called “cube-splitting” of 𝛯𝛯𝑚𝑚+1

𝑛𝑛 . 
(2) The “cube-splitting” of 𝛯𝛯𝑚𝑚+1𝑛𝑛  keeps the monotonicity property in the following way: let 𝐹𝐹 be a 

monotone binary function defined on 𝛯𝛯𝑚𝑚+1
𝑛𝑛 , then either 𝑁𝑁𝐹𝐹 ∩ ℰ𝑖𝑖 is empty, or it satisfies the 

binary monotonicity property, i.e., for arbitrary vertex 𝑎𝑎 of 𝑁𝑁𝐹𝐹 ∩ ℰ𝑖𝑖, all vertices of ℰ𝑖𝑖 greater 
than 𝑎𝑎, also belong to 𝑁𝑁𝐹𝐹 ∩ ℰ𝑖𝑖 (for 𝑖𝑖 = 1, ⋯ , 𝑛𝑛). 

By integrating (1) and (2), a novel monotone recognition method has been proposed in [6].  
 
 
2.1 Definitions/descriptions 

 
For each vertex 𝑉𝑉𝑖𝑖 = (𝑣𝑣𝑖𝑖1, ⋯ , 𝑣𝑣𝑖𝑖𝑛𝑛) of 𝐻𝐻� we compose the following set: 

ℰ𝑉𝑉𝑖𝑖 = {(𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) ∈ 𝛯𝛯𝑚𝑚+1
𝑛𝑛 |𝑎𝑎𝑗𝑗 ∈ {𝑣𝑣𝑖𝑖𝑗𝑗, 𝑚𝑚 − 𝑣𝑣𝑖𝑖𝑗𝑗} for all 𝑗𝑗, 1 ≤ 𝑗𝑗 ≤ 𝑛𝑛}, 

and call ℰ𝑉𝑉𝑖𝑖 the vertical equivalence class of 𝑉𝑉𝑖𝑖. 
ℰ𝑉𝑉𝑖𝑖 contains a unique vertex from 𝐻𝐻�, - this is the vertex with all coordinates ≥ 𝑚𝑚/2; and 
contains a unique vertex from 𝐻𝐻�, - this is the vertex with all coordinates ≤ 𝑚𝑚/2. The remaining 
vertices of ℰ𝑉𝑉𝑖𝑖 can be obtained by component value inversions (with respect to 𝑚𝑚). ℰ𝑉𝑉𝑖𝑖 ∩ ℰ𝑉𝑉𝑗𝑗 =
∅ for different vertices 𝑉𝑉𝑖𝑖 and 𝑉𝑉𝑗𝑗 of 𝐻𝐻�. In this manner 𝛯𝛯𝑚𝑚+1

𝑛𝑛  can be split into �𝐻𝐻�� disjoint sets 
/equivalence classes/ uniquely defined by the elements of 𝐻𝐻� (or 𝐻𝐻�). 

The number of elements of ℰ𝑉𝑉𝑖𝑖 varies between 2
0 and 2𝑛𝑛 depending on the number of 

components of 𝑉𝑉𝑖𝑖 differing from 𝑚𝑚/2. Indeed, if 𝑘𝑘 denotes the number of components of 𝑉𝑉𝑖𝑖 
differing from 𝑚𝑚/2, i.e. 𝑘𝑘 = �{𝑣𝑣𝑖𝑖𝑗𝑗|𝑣𝑣𝑖𝑖𝑗𝑗 ≠ (𝑚𝑚 − 𝑣𝑣𝑖𝑖𝑗𝑗)}�, then �ℰ𝑉𝑉𝑖𝑖� = 2

𝑘𝑘. Notice that 𝑘𝑘 = 𝑛𝑛 always 
for odd 𝑚𝑚. For example, Fig. 2 demonstrates ℰ(3,4,3), ℰ(2,3,4) and ℰ(4,2,2) in 𝛯𝛯5

3.  
 

 
 

Fig. 2. Examples of cubes in a cube split of 𝛯𝛯5
3. 

322

222

122

231

232

233 224

203302

241

311

321

331

111

121

131

102

142

113

123

133313

323

333 243

201

342

444

443 434 344

442 433 424 343 334 244

432 423 324 234

422 332 242

223

144

044134143314404413341431440

441 414

430 431 340 412 403 304 214 124 043 034

024033114042204132213141303312240402330411420

410

400

401 320 230 221 140 212 041 032 104 023 014

004013022103031112040202130211220301310

300 210 120 030 021 012 003

002011020101110200

100 010 001

000



L. Aslanyan and  H. Sahakyan 
 

47 

For every vertex (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) of the equivalence class ℰ𝑉𝑉𝑖𝑖, we distinguish its sub-list of all 
coordinates accepting a value differing from 𝑚𝑚/2, let this be the list: (𝑎𝑎𝑠𝑠1, ⋯ , 𝑎𝑎𝑠𝑠𝑘𝑘). This list 
exactly fits the list of all coordinates of 𝑉𝑉𝑖𝑖 that are different from 𝑚𝑚/2. The reminder part of 
coordinates accepts the only value 𝑚𝑚/2 over the 𝑉𝑉𝑖𝑖, as well as over the whole set of vertices of 
ℰ𝑉𝑉𝑖𝑖. Now, identifying (𝑎𝑎𝑠𝑠1, ⋯ , 𝑎𝑎𝑠𝑠𝑘𝑘) with the binary sequence 𝛽𝛽 = (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) of length 𝑘𝑘 such 
that 𝛽𝛽𝑗𝑗 = 1 if and only if 𝑎𝑎𝑠𝑠𝑗𝑗 > 𝑚𝑚/2, - we map (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) into the vertex 𝛽𝛽 = (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) of 
the 𝑘𝑘-dimensional binary cube 𝐸𝐸𝑘𝑘. In this manner, we obtain a 1-1 mapping 𝑀𝑀: ℰ𝑉𝑉𝑖𝑖 ⟶ 𝐸𝐸

𝑘𝑘. The 
vertex of ℰ𝑉𝑉𝑖𝑖 with all coordinates < 𝑚𝑚/2 is mapped into the vertex (0, ⋯ ,0) of 𝐸𝐸

𝑘𝑘 (on the 0-th 
layer); the vertex of  ℰ𝑉𝑉𝑖𝑖 with all coordinates  > 𝑚𝑚/2 is mapped into the vertex (1, ⋯ ,1) of 𝐸𝐸

𝑘𝑘 
(on the 𝑛𝑛-th layer); and, in general, all vertices of ℰ𝑉𝑉𝑖𝑖, which have  𝑙𝑙 coordinates > 𝑚𝑚/2 
(consequently, 𝑚𝑚 − 𝑙𝑙 coordinates < 𝑚𝑚/2), are mapped into the vertices of 𝑙𝑙-th layer of 𝐸𝐸𝑘𝑘. 

Hereafter, all structures (vertices, chains, cubes, functions, etc.) in 𝛯𝛯𝑚𝑚+1
𝑛𝑛   will be referred 

to as origin; and all structures (vertices, chains, cubes, functions, etc.) in binary cubes will be 
referred to as induced. 

For example, the induced binary cubes for ℰ(3,4,3), ℰ(2,3,4) and ℰ(4,2,2), are given in Figure 
3, (a), (b), and (c), correspondingly.  

 
 

 
(a)                     (b)          (c) 

 
Fig. 3. 

 
2.2  The Algorithmic Framework 

 
Let 𝐹𝐹 be a monotone binary function (which should be recognized with the help of an oracle), 
defined on 𝛯𝛯𝑚𝑚+1

𝑛𝑛 , and let 𝑁𝑁𝐹𝐹 denote its set of units of function 𝐹𝐹. 
 
Algorithm 1 
In a theoretical level description, the algorithm implements the following steps: 

1. Apply the cube-splitting on 𝛯𝛯𝑚𝑚+1𝑛𝑛  and let ℰ1, ⋯,.ℰ|𝐻𝐻�| be the equivalence classes of the upper 
homogeneous elements. 

000

001010100

101110

111

011

01

00

10

11

0

1



Notes on Monotone Recognition in-Multi-Valued Grids 
 

48 

2. Compose the corresponding induced binary cube 𝐸𝐸𝑖𝑖 for every ℰ𝑖𝑖. 
3. Apply the Hansel’s algorithm to recognize the induced Boolean function 𝑓𝑓𝑖𝑖, defined on 𝐸𝐸𝑖𝑖 as 

follows: for every 𝛽𝛽 ∈ 𝐸𝐸𝑖𝑖,  𝑓𝑓𝑖𝑖(𝛽𝛽) = 1 if and only if 𝐹𝐹(𝑏𝑏) = 1, where 𝑏𝑏 is the origin of 𝛽𝛽 in 
𝛯𝛯𝑚𝑚+1
𝑛𝑛  (for 𝑖𝑖 = 1, ⋯ , �𝐻𝐻��).  

4. Transfer the recognition results into the 𝛯𝛯𝑚𝑚+1𝑛𝑛 . 
 

3. Implementation 
 
3.1 Implementation details of Step 1 and Step2 

 
We consider the lexicographic ordering of the vertices of �𝐻𝐻��, where the smallest numerical 
values of coordinates are coming first. Thus, the smallest vertex of 𝐻𝐻� in this ordering is 
(m+1

2
, m+1

2
, ⋯ , m+1

2
) if 𝑚𝑚 is odd, and it is the vertex(𝑚𝑚

2
, 𝑚𝑚
2

, ⋯ , 𝑚𝑚
2

), if 𝑚𝑚 is even; the greatest 
vertex is (𝑚𝑚, 𝑚𝑚, ⋯ , 𝑚𝑚). Henceforth, we will assume that 𝐻𝐻� = {𝑉𝑉1, 𝑉𝑉2, ⋯ , 𝑉𝑉𝐻𝐻�} is the 
lexicographically ordered set of upper homogeneous elements.  

The cube splitting of 𝛯𝛯𝑚𝑚+1
𝑛𝑛  assumes that we compose for every vertex 𝑉𝑉𝑖𝑖 = (𝑣𝑣𝑖𝑖1, ⋯ , 𝑣𝑣𝑖𝑖𝑛𝑛) of 𝐻𝐻� 

its vertical equivalence class ℰ𝑉𝑉𝑖𝑖, and the corresponding induced binary cube to this.  
But at this point we do not need to compose and keep (and further to map to the binary cube) 

the whole set ℰ𝑉𝑉𝑖𝑖; instead, with every vertex 𝑉𝑉𝑖𝑖 = (𝑣𝑣𝑖𝑖1, ⋯ , 𝑣𝑣𝑖𝑖𝑛𝑛) of 𝐻𝐻� we will keep the following 
parameters: 

- the number 𝜏𝜏𝑉𝑉𝑖𝑖 of coordinates of 𝑉𝑉𝑖𝑖 differing from 𝑚𝑚/2,  - this will determine the size of the 
induced binary cube 𝐸𝐸𝑖𝑖. When 𝑉𝑉𝑖𝑖, that is the issue, is evident, we will just use the notion 𝜏𝜏 for 
this, 

- the positions of coordinates differing from 𝑚𝑚/2, we denote it by the vector 𝑉𝑉𝑖𝑖≠, and  
- the values of coordinates differing from  𝑚𝑚/2, we denote as the vector 𝑉𝑉𝑖𝑖#. 

𝜏𝜏, 𝑉𝑉𝑖𝑖≠, and 𝑉𝑉𝑖𝑖# will allow the easy reverse mapping, 𝑅𝑅𝑀𝑀 ∶ 𝐸𝐸𝜏𝜏 ⟶ ℰ𝑉𝑉𝑖𝑖, i.e., will allow to recover 
ℰ𝑉𝑉𝑖𝑖.  

For example, with the vertex (2,3,4) of 𝛯𝛯5
3 we keep:  

- numerical value 2, - this is the number of its coordinates differing from 𝑚𝑚/2, 
- indexes 2,3 - these are the coordinate indexes, where the values are differing from 𝑚𝑚/2, 
- and 3,4 are the values at the coordinates 2 and 3. 

ℰ(2,3,4) is mapped into the 2-dimensional binary cube 𝐸𝐸2 according to 2nd and 3rd coordinates of 
(2,3,4), and the accompanying vectors are 𝑉𝑉𝑖𝑖≠ = (2,3) and 𝑉𝑉𝑖𝑖# = (3,4).  
The reverse mapping is as follows: given the pair (2,3,4) and 𝐸𝐸2 or alternatively, 𝑉𝑉𝑖𝑖≠, 𝑉𝑉𝑖𝑖# and 
𝐸𝐸2. Consider an arbitrary vertex of 𝐸𝐸2, for example, let 𝛽𝛽� = (1,0), then it follows that the origin 
of 𝛽𝛽� in ℰ(2,3,4) is 𝑎𝑎� = (2,3,0), because: 

- the first component, missing at 𝑉𝑉𝑖𝑖≠, must be 𝑚𝑚/2, that is, 𝑎𝑎1 = 2,  
- the second component should not be inverted in accord to 𝛽𝛽� = (1,0), and, thus, 𝑎𝑎2 = 3, 
- the third component should be inverted, and thus, 𝑎𝑎3 = 4 − 4 = 0. 

In general, let (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) be an arbitrary vertex of the 𝑘𝑘-dimensional binary cube 𝐸𝐸𝑘𝑘, and let 
(𝑣𝑣1, ⋯ , 𝑣𝑣𝑛𝑛) be the upper homogeneous vector of the origin of 𝐸𝐸𝑘𝑘, and suppose that 𝑠𝑠1, ⋯ , 𝑠𝑠𝑘𝑘 are 
its coordinates differing from 𝑚𝑚/2. Then, the origin of (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) is (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛), where: 
 

 



L. Aslanyan and  H. Sahakyan 
 

49 

𝑎𝑎𝑠𝑠𝑗𝑗 = �
𝑣𝑣𝑠𝑠𝑗𝑗 𝑖𝑖𝑓𝑓 𝛽𝛽𝑗𝑗 = 1  

𝑚𝑚 − 𝑣𝑣𝑠𝑠𝑗𝑗𝑖𝑖𝑓𝑓 𝛽𝛽𝑗𝑗 = 0         
for 𝑗𝑗 = 1, ⋯ , 𝑘𝑘    (1) 

                 𝑎𝑎𝑖𝑖 = 𝑚𝑚/2 for 𝑖𝑖 ≠ 𝑠𝑠1, ⋯ , 𝑠𝑠𝑘𝑘. 
 
 
 

3.2  Implementation Details of Step 3 and Step 4 
 
In this part, Algorithm 1 recognizes monotone Boolean functions in the �𝐻𝐻�� number of binary 
cubes of different sizes (some of the functions might be identically 0, but we do not know this 
fact beforehand), by applying the Hansel’s algorithm. 

Also at this step, we will not deal with the binary cubes themselves, and we will be using 
the chain algebras, and therefore, we have to map (by the reverse mapping) all induced structures 
(vertices, functions, chains, etc.) into their origins in 𝛯𝛯𝑚𝑚+1

𝑛𝑛 .  
For example, consider some monotone Boolean function 𝑓𝑓𝑖𝑖 on a 𝑘𝑘-dimensional binary 

cube. If we obtain the value 𝑓𝑓𝑖𝑖(𝛽𝛽�) on some vertex 𝛽𝛽� (in the process of the Hansel’s algorithm), 
and know its origin upper homogeneous vertex (𝑣𝑣1, ⋯ , 𝑣𝑣𝑛𝑛) and also its coordinates differing 
from 𝑚𝑚/2 (let they be 𝑠𝑠1, ⋯ , 𝑠𝑠𝑘𝑘), then we can set that 𝐹𝐹(𝑎𝑎�) = 𝑓𝑓𝑖𝑖�𝛽𝛽��, where the coordinate values 
of 𝑎𝑎� are defined in accord to (1).  

Similarly, we can map chains from the induced binary cubes into the 𝛯𝛯𝑚𝑚+1
𝑛𝑛 . 

For example, the maximum length chain <(000), (100), (110), (111)> in the cube in 
Figure 2 (a) (which is induced to ℰ(3,4,3)), is mapped to the origin chain <(101), (301), (341), 
(343)> in 𝛯𝛯𝑚𝑚+1

𝑛𝑛 . 
Upon receipt of the oracle’s response for a given vertex of the binary cube - the response 

is mapped into the origin vertex of 𝛯𝛯𝑚𝑚+1
𝑛𝑛 . Certainly, the response value could also be extended 

by the monotonicity property to the other relevant vertices of  𝛯𝛯𝑚𝑚+1
𝑛𝑛 . But in this research we 

prefer and emphasize the opportunity of the parallel implementation of the recognition 
algorithms in all the induced binary cubes, and so we keep them as separate nonintersecting 
processes. 
 

4. Small Number of Units 
 
Note that Algorithm 1 is worth applying when a large number of unit vertices of the monotone 
function appear in the upper homogeneous area 𝐻𝐻�.  

However, in some cases, mostly coming from applications, the function to be recognized has 
a small number of unit vertices in the upper area 𝐻𝐻�, or its complement has  a small number of 
zero vertices in the lower homogeneous area 𝐻𝐻�. In the latter case we can recognize the 
complement of the monotone function. For this reason, the following points will be taken into 
account: 
- ℰ𝑉𝑉𝑖𝑖 can be defined for each vertex of 𝐻𝐻� (obviously we will obtain the same set). In the 

example given in Figure 2 the highlighted sets of 𝐻𝐻� will demonstrate ℰ(1,0,1), ℰ(2,1,0) and 
ℰ(0,2,2), as well.  

- The mapping 𝑀𝑀: ℰ𝑉𝑉𝑖𝑖 ⟶ 𝐸𝐸
𝑘𝑘 will be defined as follows: for every vertex (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛) of ℰ𝑉𝑉𝑖𝑖 

let (𝑎𝑎𝑠𝑠1, ⋯ , 𝑎𝑎𝑠𝑠𝑘𝑘) denote its subsequence with all coordinates differing from 𝑚𝑚/2. Identify 
(𝑎𝑎𝑠𝑠1, ⋯ , 𝑎𝑎𝑠𝑠𝑘𝑘) with the binary sequence 𝛽𝛽 = (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) of length 𝑘𝑘 such that 𝛽𝛽𝑗𝑗 = 1 if and 
only if 𝑎𝑎𝑠𝑠𝑗𝑗 < 𝑚𝑚/2. The vertex of  ℰ𝑉𝑉𝑖𝑖 with all coordinate values < 𝑚𝑚/2 is mapped into the 



Notes on Monotone Recognition in-Multi-Valued Grids 
 

50 

vertex (1, ⋯ ,1) of 𝐸𝐸𝑘𝑘, - this is on the 𝑛𝑛-th layer; the vertex of  ℰ𝑉𝑉𝑖𝑖 with all coordinate values  
< 𝑚𝑚/2 is mapped into the vertex (0, ⋯ ,0) of 𝐸𝐸𝑘𝑘, - this is on the 0-th layer; and, in general, 
all vertices of ℰ𝑉𝑉𝑖𝑖 which have 𝑙𝑙 coordinates < 𝑚𝑚/2 (consequently, 𝑚𝑚 − 𝑙𝑙 coordinates >
𝑚𝑚/2) are mapped into the vertices of 𝑙𝑙-th layer of 𝐸𝐸𝑘𝑘. 

- The reverse mapping: 𝑅𝑅𝑀𝑀: 𝐸𝐸𝑖𝑖 ⟶ ℰ𝑉𝑉𝑖𝑖 will be implemented as follows: let (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) be an 
arbitrary vertex of the 𝑘𝑘-dimensional binary cube 𝐸𝐸𝑘𝑘, and let (𝑣𝑣1, ⋯ , 𝑣𝑣𝑛𝑛) be the lower 
homogeneous vector of the origin of 𝐸𝐸𝑘𝑘, where 𝑠𝑠1, ⋯ , 𝑠𝑠𝑘𝑘 are coordinates differing from 𝑚𝑚/
2. 

 
Then the origin of (𝛽𝛽1, ⋯ , 𝛽𝛽𝑘𝑘) is (𝑎𝑎1, ⋯ , 𝑎𝑎𝑛𝑛), where: 
 

𝑎𝑎𝑠𝑠𝑗𝑗 = �
𝑣𝑣𝑠𝑠𝑗𝑗 𝑖𝑖𝑓𝑓 𝛽𝛽𝑗𝑗 = 0

𝑚𝑚 − 𝑣𝑣𝑠𝑠𝑗𝑗𝑖𝑖𝑓𝑓 𝛽𝛽𝑗𝑗 = 1       
for 𝑗𝑗 = 1, ⋯ , 𝑘𝑘    (2) 

                 𝑎𝑎𝑖𝑖 = 𝑚𝑚/2 for 𝑖𝑖 ≠ 𝑠𝑠1, ⋯ , 𝑠𝑠𝑘𝑘. 
 
 

4.1  Constraints  
 

Consider the application, which is the generalized model of the known association rule mining - 
in case where in addition to the presence or absence of elements in itemsets, the number of their 
repetitions is also included. The details are given in [7]. Here we highlight the following 
constraints/restrictions that may appear with this problem. In terminology of supermarket basket 
analysis, here we distinguish two postulations: some item exists in the current basket, and 
second, which is the actual number of that item in the basket. 

Let 𝑎𝑎𝑖𝑖 be the repetition number of the 𝑖𝑖-th element, for 𝑖𝑖 = 1, ⋯ , 𝑛𝑛.  
(1) the classic case is the (0,1) vector of item indicators in baskets, basket inventory. 
(2) 𝑎𝑎1 + ⋯ + 𝑎𝑎𝑛𝑛 ≤ 𝑟𝑟, - the summary number of elements’ repetitions (the basket volume) is 

restricted by 𝑟𝑟,  
(3) 𝑎𝑎𝑖𝑖 ≤ 𝑟𝑟𝑖𝑖, -the repetition number of each 𝑎𝑎𝑖𝑖 is restricted by 𝑟𝑟𝑖𝑖, the item purchase restriction. 
 
In these cases, the problem deals with the recognition of monotone functions, where: 
(2) the zeros of the function appear in lower layers of the multivalued grid, 
(3) the zeros of the function appear in some homogeneous bottom area of the grid.  

 
In both cases it is more efficient to use the second algorithmic scheme of [6].  
The idea is as follows. Let 𝐹𝐹 be a monotone function defined on 𝛯𝛯𝑚𝑚+1

𝑛𝑛 . First we note that 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻� 
satisfies the monotonicity property, i.e., for arbitrary 𝑎𝑎, 𝑏𝑏 of  𝐻𝐻�,  if 𝑎𝑎 ≥ 𝑏𝑏  then 𝐹𝐹(𝑎𝑎) ≥ 𝐹𝐹(𝑏𝑏). 
 
Algorithm 2 

1. Firstly identify the part of the monotone function belonging to 𝐻𝐻� by one of the known 
resources of identification of monotone functions, and thus, reduce the size of the multi-
valued grid. As a result we obtain 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�. 

2. Apply the cube-splitting according to 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�, that considers the vertical equivalence 
classes ℰ1, ⋯,.ℰ|𝑁𝑁𝐹𝐹∩𝐻𝐻�| only for the vertices of 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�.  

3. Implement 2-4 Steps of Algorithm 1. 
 

The algorithm can easily be adjusted for the identification of the complement of 𝐹𝐹 in 𝛯𝛯𝑚𝑚+1
𝑛𝑛 . 



L. Aslanyan and  H. Sahakyan 
 

51 

 
4.2  Resources  
 
To implement Step 1 of Algorithm 2 we have the following resources of identification of 
monotone functions in 𝐻𝐻�. 

a) The first resource is the known algorithm by V. Alexeyev [2]. We notice that applying 
the algorithm to identification of monotone functions on 𝐻𝐻� (instead of 𝛯𝛯𝑚𝑚+1

𝑛𝑛 ) is a significant 
reduction of the work. The complexity of the algorithm 𝑈𝑈0 on 𝐻𝐻� will be:  

 
𝑇𝑇(𝑈𝑈0) ≤ |𝑀𝑀1| + �𝑙𝑙𝑙𝑙𝑙𝑙2(

𝑚𝑚
2

)� ∙ |𝑁𝑁1|,  
 
where 𝑀𝑀1 and 𝑁𝑁1 are the middle layers of 𝐻𝐻�, defined accordingly. 
 

b) The second resource that we may use, is - applying the cube-splitting itself for identifying 
the function on 𝐻𝐻�. We define the upper homogeneous area  𝐻𝐻�� of 𝐻𝐻�,: this is the set of all elements 
of 𝛯𝛯𝑚𝑚+1

𝑛𝑛  with all coordinate values ≥ 3𝑚𝑚/4; then 
1. Apply the cube-splitting on 𝐻𝐻� and find ℰ1, ⋯,.ℰ𝐻𝐻��, equivalence classes according to the 

elements of  𝐻𝐻��. 
2. Compose the corresponding induced binary cube 𝐸𝐸𝑖𝑖 for every ℰ𝑖𝑖. 
3. Apply the Hansel’s algorithm to recognize the induced Boolean function 𝑓𝑓𝑖𝑖, defined on 

𝐸𝐸𝑖𝑖 as follows: for every 𝛽𝛽 ∈ 𝐸𝐸𝑖𝑖,  𝑓𝑓𝑖𝑖(𝛽𝛽) = 1 if and only if 𝐹𝐹(𝑏𝑏) = 1, where 𝑏𝑏 is the 
origin of 𝛽𝛽 in 𝐻𝐻� (for 𝑖𝑖 = 1, ⋯ , �𝐻𝐻���).  

4. Transfer the recognition results to 𝐻𝐻�. 
At this point we find 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�, and then continue with: 

5. Apply the cube-splitting according to 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�, that is find the vertical equivalence 
classes ℰ1, ⋯,.ℰ|𝑁𝑁𝐹𝐹∩𝐻𝐻�| only for the vertices of 𝑁𝑁𝐹𝐹 ∩ 𝐻𝐻�.  

6. Implement 2-4 Steps of Algorithm 1. 
 

c) The cube-splitting can be applied recursively. 
The following resource is also worth mentioning that can be used in all cases/algorithms. This is 
the growing technique [8] in monotone Boolean function recognition and chain computation 
algebra [9]. 
 
 
5. Conclusion 
 
The problem of query based algorithmic recognition of monotone binary functions defined in 
multi-valued grids is known as a hard problem. It was investigated by V. Korobkov, V. 
Alekseev, A.Serjantov, and others. It is known a chain-split type algorithm developed by V. 
Alekseev, where the complexity estimates were given in terms of sizes of the middle layers of 
the grid. A novel method of identification of monotone binary functions based on the partitioning 
of the grid into discrete structures isomorphic to binary cubes was proposed in our recent work, 
where a theoretical level description of two algorithmic schemes was introduced. This paper 
provides the implementation details of the algorithms, as well as focuses on the recognition of 
monotone binary functions with a small number of units /or zeros/ distributed in homogeneous 
areas of the grid. 



Notes on Monotone Recognition in-Multi-Valued Grids 
 

52 

Acknowledgement 
This work is partially supported by the grant № 18T-1B407 of the Science Committee of the 
Ministry of Education and Science of Armenia. 
 
 
References 
 
[1] V.Korobkov, On Monotone Functions of Algebra of Logic, Prob. Cyb, 13, 1965.  
[2] V.Alekseev, “On deciphering of some classes of monotone many valued functions”, USSR 

Computational Mathematics and Mathematical Physics, vol. 16, no. 1, pp. 189-198, 1976. 
[3] A.Serjantov, “Optimal algorithm for deciphering of some classes of monotone 

functions”,Journal of Computational Mathematics and Math. Physics, vol. 23, no. 1, pp. 
206-212, 1983.  

[4] N.Zolotyk and A.Chirkov, “On the complexity of deciphering of threshold functions of 
many-valued logic”, Proceedings of the XI International seminar ”Discrete mathematics 
and its applications”, Commemorate on the 80th anniversary of academician Lupanov, pp. 
63-77, 2012. 

[5] G. Hansel, “Sur le nombre des fonctiones booleennes monotones de n variables”, C. R. Acad. 
Sci.p. 262, 1966. 

[6] L. Aslanyan and H. Sahakyan, “The splitting technique in monotone recognition”, Discrete 
Applied Mathematics, vol. 216,pp. 502–512, 2017. 

[7] L. Aslanyan and H. Sahakyan, “Cube-split technique in quantitative association rule 
mining”, Information Theories and Applications, vol. 24, no. 3, pp. 3-20, 2017. 

[8] L. Aslanyan and R. Khachatryan, “Association rule mining with n-dimensional unit cube 
chain split technique”, Information Theories and Applications, vol. 1, no. 2, pp. 108-125, 
2008. 

[9] G.Tonoyan, “The successive splitting of vertices of an n-dimensional unit cube into chains 
and decoding problems of monotonic Boolean functions”, USSR Computational 
Mathematics and Mathematical Physics, vol. 19, no. 6, pp. 179-191, 1979. 

 
 

 
Submitted 24.07.2019, accepted 28.11.2019. 

 
 

Մոնոտոն ֆունկցիայի ճանաչում բազմարժեք ցանցում 
 

Լևոն Հ. Ասլանյան և Հասմիկ Ա. Սահակյան 
 

ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ 
e-mail: lasl@sci.am,  hsahakyan@sci.am 

 
Ամփոփում 

 
Այս շարքի նախորդ աշխատանքներում առաջարկվել է մոնոտոն բինար ֆունկցիայի 
վերծանման նոր մոտեցում՝ հիմնված բազմարժեք բազմաչափ ցանցի 
խորանարդատիպ տրոհման մեթոդի վրա, որտեղ տեսական մակարդակում 

http://www.sciencedirect.com/science/journal/00415553
http://www.sciencedirect.com/science/journal/00415553
http://www.sciencedirect.com/science/journal/00415553
http://www.sciencedirect.com/science/journal/00415553
http://www.sciencedirect.com/science/journal/00415553/19/6
mailto:lasl@sci.am
mailto:hsahakyan@sci.am


L. Aslanyan and  H. Sahakyan 
 

53 

առաջարկվել է խնդրի լուծման երկու ալգորիթմ /ալգորիթմական սխեմա/: Ներկա 
աշխատանքում տրվում են այդ ալգորիթմների իրականացման մանրամասները, 
ինչպես նաև դիտարկվում է այն դեպքը, երբ մոնոտոն ֆունկցիան ունի  փոքր թվով 
մեկ արժեքի գագաթներ: 
Բանալի բառեր` Մոնոտոն ֆունկցիայի ճանաչում, բազմարժեք ցանց, 
խորանարդատիպ տրոհում: 
 

 

Заметки о монотоннoм распознавании в многозначных 
решетках 

 
Левон А. Асланян и Асмик А. Саакян 

 
Институт проблем информатики и автоматизации НАН РА 

e-mail: lasl@sci.am,  hsahakyan@sci.am 
 

Аннотация 
 

     Новый подход монотонного распознавания на основе разбиения многозначной решетки 
на дискретные структуры, изоморфные бинарным кубам (метод “кубического разбиения”) 
предложен в серии последних работ, где на теоретическом уровне дано описание двух 
алгоритмов /алгоритмических схем/ решения задачи. В данной статье приводится 
подробное описание деталей реализации этих алгоритмов, а также рассматривается случай 
распознавания монотонной функции с небольшим числом единиц, что связано с рядом 
практических приложений. 
      Ключевые слова: распознавание монотонной функции, многозначная решетка, 
кубическое разбиение. 

 
 

mailto:lasl@sci.am
mailto:hsahakyan@sci.am

	2. The Cube-Splitting Technique
	2.1 Definitions/descriptions
	2.2  The Algorithmic Framework

	3. Implementation
	3.1 Implementation details of Step 1 and Step2
	3.2  Implementation Details of Step 3 and Step 4

	4. Small Number of Units
	4.1  Constraints
	4.2  Resources