Kerven Durdymyradov, Mikhail Moshkov
Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia.
DOI: 10.4236/jilsa.2025.173013   PDF    HTML   XML   113 Downloads   467 Views   Citations

Abstract

We consider various tasks of recognizing properties of DRSs (Decision Rule Systems) in this paper. As solution algorithms, DDTs (Deterministic Decision Trees) and NDTs (Nondeterministic Decision Trees) are used. An NDT can be considered as a representation of a DRS that satisfies the conditions of the considered task and covers all potential inputs. It has been shown that the minimum depth of a DDT solving the task does not exceed the square of the minimum depth of an NDT. The growth of the minimum number of nodes in DDTs and NDTs can be exponential with the size of the original DRSs. Therefore, in the general case, it is better to simulate the behavior of the DT (Decision Tree) on the given tuple of feature values rather than building the entire tree. We propose a greedy algorithm for such modeling and study its efficiency for a class of tasks of recognizing properties of DRSs. The obtained results may be of interest for data analysis in which both DRSs and DTs are intensively studied. In particular, these results make one think about the possibilities of transforming DRSs into DTs.

Keywords

Deterministic Decision Tree, Nondeterministic Decision Tree, Decision Rule System

Share and Cite:

1. Introduction

DRSs (Decision Rule Systems) [1]-[5] and DTs (Decision Trees) [6]-[9] serve as common models for structuring and representing the knowledge. They act as classifiers that predict solutions for unseen instances, and operate as algorithms addressing tasks in combinatorial optimization, fault diagnosis, and related domains. Among classification and knowledge representation techniques, both DTs and DRSs stand out for their high level of interpretability [10]. Exploring the relationships between DTs and DRSs represents an important research direction in computer science.

In this paper, we study DDTs (Deterministic Decision Trees) and NDTs (Nondeterministic Decision Trees) for solving tasks related to recognizing properties of DRSs. Note that an NDT solving such a task, can be considered as a representation of a DRS that is true for this task and covers the whole set of inputs.

Compared to classical decision tree models, which rely on information-theoretic criteria (e.g., entropy or Gini index) and typically require labeled data, our approach uses a syntactic method that operates directly on a known DRS without the need for input data. Moreover, our framework preserves full transparency of decision paths, thereby maintaining a high level of interpretability.

In the present paper, we continue to develop a syntactic approach to solving the tasks under consideration, proposed in [11] [12]. It assumes that the DRS is known, but the input data is unavailable. The results of previous studies in this area are summarized in the book . Compared to , this paper, which extends two conference papers [14] [15], considers a wider range of tasks related to recognizing the properties of DRSs.

Let $S$ be a finite DRS represented in the form

$\left(f_{i_1}=d_1\right)\wedge \cdots \wedge \left(f_{i_m}=d_m\right)\to d,$

where $f_{i_1},\cdots ,f_{i_m}$ are features, $d_1,\cdots ,d_m$ represent feature values selected from the set $E_k=\left\{0,\cdots ,k-1\right\}$ , where $k\ge 2$ , and $d$ denotes a nonnegative integer serving as the decision.

Let $f_1,\cdots ,f_n$ be all features from the DRs (Decision Rules) in the DRS $S$ , and $\overline{b}=\left(b_1,\cdots ,b_n\right)\in E_k^n$ be a tuple of values of the features $f_1,\cdots ,f_n$ . The considered DR is called applicable for the tuple $\overline{b}$ when its left part is true for this tuple, i.e., when $b_{i_1}=d_1,\cdots ,b_{i_m}=d_m$ .

A solution map is a function $\phi$ that associates a tuple $\overline{b}$ of values of features from $S$ with a corresponding value $\phi \left(\overline{b}\right)$ , referred to as the solution. Let us consider examples of solution maps (more examples can be found in Sect. 2.1):

• $\phi \left(\overline{b}\right)=1$ if there exists a DR from $S$ that is applicable for the tuple $\overline{b}$ and $\phi \left(\overline{b}\right)=0$ otherwise.

• $\phi \left(\overline{b}\right)$ is the set of all DRs in $S$ which are applicable for the tuple $\overline{b}$ .

• $\phi \left(\overline{b}\right)$ is the set of decisions from the right part of DRs in $S$ which are applicable for the tuple $\overline{b}$ .

We study the task of finding $\phi \left(\overline{b}\right)$ , where $\overline{b}\in E_k^n$ is a tuple of feature values from $S$ . We denote this task as $T\left(\phi ,S,k\right)$ . It is important to note that while solving the task $T\left(\phi ,S,k\right)$ , the tuple $\overline{b}$ is not directly accessible. To determine the value of a feature, we need to find it for the given input, which can be an expensive procedure. To minimize the number of queries related to feature values, we consider DDTs and NDTs solving the task $T\left(\phi ,S,k\right)$ .

We pay special attention to the task of All Applicable Rules (AAR task) for which $\phi \left(\overline{b}\right)$ is the set of all DRs from $S$ that are applicable for the tuple $\overline{b}$ . For this task, we consider DRS examples where DDTs and NDTs can solve the AAR task with minimum depths much smaller than the number of distinct features in $S$ . In such a situation, the use of DTs seems appropriate. We also consider examples of DRSs, in which the minimal number of nodes in DDTs and NDTs solving the AAR task grows exponentially with the size of the DRSs. Therefore, in general, instead of constructing the entire DT, we should model its operation on a given tuple $\overline{b}$ using a sufficiently efficient algorithm. Note that similar examples were considered in the book [13].

First, we investigate how the minimum depths of DDTs and NDTs relate when solving the task $T\left(\phi ,S,k\right)$ . We use $h^d\left(\phi ,S,k\right)$ to represent the minimal depth of a DDT solving this task, and $h^a\left(\phi ,S,k\right)$ for the minimal depth of an NDT. We show the inequalities $h^a\left(\phi ,S,k\right)\le h^d\left(\phi ,S,k\right)\le h^a{\left(\phi ,S,k\right)}^2$ . These bounds were obtained in the conference paper [15].

To obtain the upper bound for $h^d\left(\phi ,S,k\right)$ , we analyze an NDT $\mathcal{G}$ that solves the task $T\left(\phi ,S,k\right)$ with depth $h^a\left(\phi ,S,k\right)$ . Using this tree, we describe the operation of a DDT $G$ , solving the same task for a given tuple $\overline{b}\in E_k^n$ , has the depth at most $h^a{\left(\phi ,S,k\right)}^2$ . It should be emphasized that this description of the DDT cannot be regarded as an efficient algorithm, since $\mathcal{G}$ may possess a substantial number of nodes. Note also that a similar upper bound was derived in [13] for functions of $k$ -valued logic, $k\ge 2$ and in [16]-[18] for Boolean functions (see [19] for details).

We additionally introduce a greedy algorithm $\mathcal{U}$ which, for a given DRS $S$ and a tuple $\overline{b}\in E_k^n$ of feature values, simulate the operation of a DDT solving the task $T\left(\phi ,S,k\right)$ on $\overline{b}$ . For this algorithm, we need to have an uncertainty measure $\gamma$ for the task $T\left(\phi ,S,k\right)$ , which is defined on the set of equation systems of the form $\alpha =\left\{f_{i_1}=d_1,\cdots ,f_{i_m}=d_m\right\}$ , such that $f_{i_1},\cdots ,f_{i_m}$ are pairwise different features from the set $\left\{f_1,\cdots ,f_n\right\}$ and $d_1,\cdots ,d_m\in E_k$ . The system of equations $\alpha$ describes information already obtained by the DT. At the beginning of the tree work, $\alpha =\varnothing$ . The DT will stop when $\gamma \left(\alpha \right)=0$ . We prove that the depth of the considered DDT is at most $h^a\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1$ .

It should be noted that this algorithm has some similarities with the one presented in Sect. 4.2 of . However, the method in operates on a decision table $T$ instead of a DRS $S$ , and uses very different measures of uncertainty, in particular, the value $P\left(T\right)$ , which counts unordered pairs of rows in $T$ having distinct decisions.

The uncertainty measure should satisfy some additional requirements, and the search for appropriate uncertainty measures is a nontrivial task. In the conference paper [14], we found a suitable uncertainty measure for the AAR task and proved all the results related to the greedy algorithm only for the AAR task. In the current paper, we extend these results to the general case of an arbitrary task $T\left(\phi ,S,k\right)$ and an appropriate uncertainty measure $\gamma$ for it.

We generalized essentially the results obtained in [14] by studying the task of recognition of applicable special subsets of the DRS $S$ . Let $W$ be a nonempty family of nonempty subsets of $S$ that are called special subsets of $S$ . We assume that, for each subset $w$ from $W$ , there exists a tuple $\overline{b}\in E_k^n$ for which all DRs from $w$ are applicable. In this case, we will say that the subset $w$ of DRs is applicable for the tuple $\overline{b}$ . We consider the following task $T\left({\phi }_W,S,k\right)$ : for a given tuple $\overline{b}\in E_k^n$ , we should find all subsets $w\in W$ that are applicable for the tuple $\overline{b}$ . For this task, we found an appropriate uncertainty measure ${\gamma }_W$ such that ${\gamma }_W(\varnothing )\le \left|W\right|n$ and showed that the algorithm $\mathcal{U}$ has polynomial time complexity depending of the sizes of the DRS $S$ and the family $W$ . The depth of a DDT, the operation of which is modeled by the algorithm $\mathcal{U}$ , does not exceed $h^a\left({\phi }_W,S,k\right)\left(\ln \left|W\right|+\ln n\right)+1$ .

The results obtained in this paper may be of interest for data analysis, in which both DRSs and DTs are intensively studied. In particular, these results make one think about the possibilities of transforming DRSs into DTs.

The structure of the paper is as follows. Section 2 provides the key definitions and notation, closely aligned with those in [13]. Section 3 explores both the possibilities and the constraints of using DTs. In Section 4, we analyze and compare the minimum depths of DDTs and NDTs. Section 5 focuses on a greedy algorithm designed to simulate the operation of a DDT. Section 6 addresses the task of identifying applicable special subsets of a DRS. Finally, Section 7 offers concluding remarks.

2. Definitions

This section introduces the fundamental definitions and notations associated with DRSs and DTs.

2.1. DRSs—Decision Rule Systems

Let ${\mathbb{N}}_0=\left\{0,1,2,\cdots \right\}$ , and define the set of features as $F=\left\{f_i:i\in {\mathbb{N}}_0\right\}$ . For any $k\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ , let $E_k=\left\{0,1,\cdots ,k-1\right\}$ .

Definition 1 We use $ES$ to denote the set of systems of equations of the following form:

$\left\{f_{i_1}=b_1,\cdots ,f_{i_m}=b_m\right\},$

where $m\in {\mathbb{N}}_0$ , $f_{i_1},\cdots ,f_{i_m}\in F$ and $b_1,\cdots ,b_m\in {\mathbb{N}}_0$ . The system will be inconsistent if there exist $t,p\in \left\{1,\cdots ,m\right\}$ such that $t\ne p$ , $i_t=i_p$ , and $b_t\ne b_p$ . Otherwise, the system will be called consistent.

Definition 2 A DR (Decision Rule) is defined as an expression of the following form:

$\left(f_{i_1}=b_1\right)\wedge \cdots \wedge \left(f_{i_m}=b_m\right)\to d,$

where $m\in {\mathbb{N}}_0\backslash \left\{0\right\}$ , $f_{i_1},\cdots ,f_{i_m}$ are pairwise different features from $F$ , and $b_1,\cdots ,b_m,d\in {\mathbb{N}}_0$ .

We denote this DR by $r$ . The value $d$ is referred to as the decision of the decision rule $r$ . The integer $m$ is called the length of $r$ and is denoted by $l\left(r\right)$ . We define $F\left(r\right)=\left\{f_{i_1},\cdots ,f_{i_m}\right\}$ as the set of features in $r$ and $K\left(r\right)=\left\{f_{i_1}=b_1,\cdots ,f_{i_m}=b_m\right\}$ . Let $V\left(r\right)$ denote the minimum integer $k\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ for which $\left\{b_1,\cdots ,b_m\right\}\subseteq E_k$ .

Definition 3 A Decision Rule System (DRS) $S$ is defined as a finite, nonempty set of DRs.

Denote $F\left(S\right)={\displaystyle {\cup }_{r\in S}F\left(r\right)}$ , $n\left(S\right)=\left|F\left(S\right)\right|$ , $L\left(S\right)={\displaystyle {\sum }_{r\in S}l\left(r\right)}$ , and $V\left(S\right)=\text{max}\left\{V\left(r\right):r\in S\right\}$ . Let $n\left(S\right)=n$ and $F\left(S\right)=\left\{f_{j_1},\cdots ,f_{j_n}\right\}$ , where $j_1<\cdots <j_n$ . For $\overline{b}=\left(b_1,\cdots ,b_n\right)\in {\mathbb{N}}_0^n$ , denote $K\left(S,\overline{b}\right)=\left\{f_{j_1}=b_1,\cdots ,f_{j_n}=b_n\right\}$ .

Definition 4 A DR $r$ from $S$ is called applicable for a tuple $\overline{b}\in {\mathbb{N}}_0^{n\left(S\right)}$ if $K\left(r\right)\subseteq K\left(S,\overline{b}\right)$ .

Definition 5 Consider a DRS $S$ and an integer $k\ge V\left(S\right)$ . A solution map for the pair $\left(S,k\right)$ is a mapping $\phi$ that assigns to each tuple $\overline{b}\in E_k^{n\left(S\right)}$ a value $\phi \left(\overline{b}\right)$ from some set. This value is interpreted as a solution. The map $\phi$ will be called degenerate if it is constant on the set $E_k^{n\left(S\right)}$ and nondegenerate otherwise.

Let $S$ be a DRS, $k\ge V\left(S\right)$ , and $\overline{b}\in E_k^{n\left(S\right)}$ . We now consider a number of examples of solution maps $\phi$ for the pair $\left(S,k\right)$ :

• $\phi \left(\overline{b}\right)=1$ if there exists a DR from $S$ that is applicable for the tuple $\overline{b}$ and $\phi \left(\overline{b}\right)=0$ otherwise.

• $\phi \left(\overline{b}\right)$ is the set of all DRs from $S$ that are applicable for the tuple $\overline{b}$ .

• $\phi \left(\overline{b}\right)$ is the number of DRs from $S$ that are applicable for the tuple $\overline{b}$ .

• $\phi \left(\overline{b}\right)$ is the set of decisions of DRs from $S$ that are applicable for the tuple $\overline{b}$ .

• $\phi \left(\overline{b}\right)$ is the minimum number $d\in {\mathbb{N}}_0$ such that the number of DRs from $S$ that are applicable for the tuple $\overline{b}$ and have $d$ as the decision is maximum.

Let $S$ be a DRS with $n\left(S\right)=n$ and $k\ge V\left(S\right)$ .

Definition 6 Let $\phi$ be a solution map for the pair $\left(S,k\right)$ . Task $T\left(\phi ,S,k\right)$ is defined as follows: for a given tuple $\overline{b}\in E_k^n$ , it is required to find the solution $\phi \left(\overline{b}\right)$ .

When addressing the task $T\left(\phi ,S,k\right)$ , it is important to note that we do not have direct access to the tuple $\overline{b}$ . To determine the value of a feature $f_i\in F\left(S\right)$ , it is necessary to compute it for the given input, which can be an expensive procedure. To minimize the number of queries related to feature values, we consider DTs for solving the task $T\left(\phi ,S,k\right)$ .

2.2. DTs—Decision Trees

A finite directed tree with a root is a finite directed tree in which exactly one node has no entering edges. This node is referred to as the root. Nodes that do not have any leaving edges are called leaf nodes, while those that are neither root nor leaf are called internal nodes. A full path in such a tree is a sequence consisting of alternating nodes and edges, where $v_1$ is the root, $v_{m+1}$ is a leaf, and for each $i=1,\cdots ,m$ , the edge $d_i$ leaves from node $v_i$ and enters to node $v_{i+1}$ .

Consider a DRS $S$ , $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , and $\phi$ be a solution map for the pair $\left(S,k\right)$ .

Definition 7 We define a DT (Decision Tree) over the task $T\left(\phi ,S,k\right)$ as a finite marked directed tree with root $\mathcal{G}$ , containing at least two nodes, and satisfying the conditions below:

• The root and edges leaving the root are not marked.

• In the tree $\mathcal{G}$ , every internal node is marked with a feature from $F\left(S\right)$ , and each leaving edge marked with a numbers from $E_k$ .

• Each leaf node of the tree $\mathcal{G}$ is marked with a solution from the set $\left\{\phi \left(\overline{b}\right):\overline{b}\in E_k^n\right\}$ .

Definition 8 A DT for the task $T\left(\phi ,S,k\right)$ is a deterministic if its root has exactly one leaving edge, and the leaving edges of every internal node are marked with pairwise distinct values.

Suppose $\mathcal{G}$ is a DT over the task $T\left(\phi ,S,k\right)$ . We denote by $FP\left(\mathcal{G}\right)$ the set of full paths in the DT $\mathcal{G}$ . Consider a full path from $\mathcal{G}$ . To this path, we associate an equation system $K\left(\right)\in ES$ . If $m=1$ and , then $K\left(\right)=\varnothing$ . Let $m\ge 2$ and, for $j=2,\cdots ,m$ , the node $v_j$ be marked with the feature $f_{i_j}$ and the corresponding edge $d_j$ be marked with the value $b_j\in E_k$ . In this case, we set $K\left(\right)=\left\{f_{i_2}=b_2,\cdots ,f_{i_m}=b_m\right\}$ . We denote by $\tau \left(\right)$ the solution associated with the leaf node $v_{m+1}$ .

Let $\mathcal{G}$ be a DT over $T\left(\phi ,S,k\right)$ , $\overline{b}\in E_k^n$ , and $\in FP\left(\mathcal{G}\right)$ . We say that a full path accepts the tuple $\overline{b}$ if $K\left(\right)\subseteq K\left(S,\overline{b}\right)$ . Furthermore, the solution is called derivable from the equation system $K\left(\right)$ if for any tuple $\overline{b}\in E_k^n$ such that the path accepts the tuple $\overline{b}$ .

Definition 9 It is called $\mathcal{G}$ solves the task $T\left(\phi ,S,k\right)$ nondeterministically if, for every tuple $\overline{b}\in E_k^n$ , there exists a path , that accepts $\overline{b}$ and, for every path $\in FP\left(\mathcal{G}\right)$ such that the system of equations $K\left(\right)$ is consistent, the solution $\tau \left(\right)$ is derivable from $K\left(\right)$ . In this case, we also refer to $\mathcal{G}$ as an NDT that solves the task $T\left(\phi ,S,k\right)$ .

Suppose $\mathcal{G}$ be a NDT solving the task $T\left(\phi ,S,k\right)$ , $\overline{b}\in E_k^n$ , and . If the path $$ accepts the tuple $\overline{b}$ , then is a consistent system of equations, the solution is derivable from , and .

Definition 10 It is called $\mathcal{G}$ solves the task $T\left(\phi ,S,k\right)$ deterministically if $\mathcal{G}$ is a DDT that solves the task $T\left(\phi ,S,k\right)$ nondeterministically. In this case, it’s called $\mathcal{G}$ is a DDT solving the task $T\left(\phi ,S,k\right)$ .

See Figure 1 for an example of a DDT and an NDT that solve the task described above.

Definition 11 We define $h\left(\right)$ as the number of internal nodes in any full path $\in FP\left(\mathcal{G}\right)$ . The value is the depth of the DT $\mathcal{G}$ .

Suppose $S$ is a DRS, $k\ge V\left(S\right)$ and $\phi$ is a solution map for the pair $\left(S,k\right)$ . We denote by $h^a\left(\phi ,S,k\right)$ the minimum depth of a NDT over the task $T\left(\phi ,S,k\right)$ , which solves this task. We denote by $h^d\left(\phi ,S,k\right)$ the minimum depth of a DDT over the task $T\left(\phi ,S,k\right)$ , which solves this task.

For example, let us consider the problem $T\left({\phi }_1,S_0,2\right)$ where $S_0=\left\{\left(a_1=0\right)\to 0,\left(a_2=1\right)\to 1\right\}$ , ${\phi }_1$ is a solution map for the pair $\left(S_0,2\right)$ : ${\phi }_1\left(\overline{b}\right)=1$ if there exists a DR from $S_0$ that is applicable for the tuple $\overline{b}$ and ${\phi }_1\left(\overline{b}\right)=0$ otherwise, from [15]. Then the decision trees depicted in Figure 1 are deterministic (left) and nondeterministic (right) decision trees that solve the considered problem.

Figure 1. Deterministic and nondeterministic decision trees solving the problem $T\left({\phi }_1,S_0,2\right)$ .

3. Preliminary Discussion

Let $S$ be a DRS, $k\ge V\left(S\right)$ , and ${\phi }_{AAR}$ be a solution map for the pair $\left(S,k\right)$ such that, for any $\overline{b}\in E_k^{n\left(S\right)}$ , ${\phi }_{AAR}\left(\overline{b}\right)$ is the set of all DRs from $S$ that are applicable for the tuple $\overline{b}$ . The task $T\left({\phi }_{AAR},S,k\right)$ is called the All Applicable Rules task. This is one of the most important tasks arising within the framework of the syntactic approach to the study of DRSs. We will study its generalizations in Sect. 6.

This section explores the possibilities and constraints of using DTs for addressing the All Applicable Rules task. Accordingly, we analyze two different sequences of DRSs. We will use the sum of lengths of DRs from $S$ , denoted by $L\left(S\right)$ , as a parameter characterizing the complexity of the DRS $S$ .

We begin by defining a sequence of DRSs, denoted as $S_m$ , where $m=2,3,\cdots$ . For each $S_m$ , the minimum depth of a DDT that solves the task $T\left({\phi }_{AAR},S_m,2\right)$ is significantly less than the number $n\left(S_m\right)$ of distinct features present in $S_m$ . The number of nodes of the corresponding DT is at most $L\left(S_m\right)$ nodes. This example demonstrates the feasibility of using DTs to solve the task $T\left({\phi }_{AAR},S_m,2\right)$ .

We then define a sequence of DRSs $Q_m$ , for $m=2,3,\cdots$ , such that the minimal number of nodes in both DDTs and NDTs solving the task $T\left({\phi }_{AAR},Q_m,2\right)$ grows exponentially with respect to the parameter $L\left(Q_m\right)$ . Consequently, constructing complete DTs becomes impractical in general. As an alternative, one can simulate the operation of a DDT on a tuple of feature values with some algorithm.

Let us begin with the first sequence of DRSs. Let $m\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ . A complete binary tree with depth $m$ is a finite directed tree with root such that every non-leaf node has exactly two leaving edges, and all full paths from the root to the leaves have length $m$ . The nodes in this tree are organized into $m+1$ layers: for each $i=0,\cdots ,m$ , the $i$ th layer consists of all nodes at distance $i$ from the root. The $i$ th level contains exactly $2^i$ nodes. In total, there are $2^m-1$ non-leaf nodes and $2^m$ leaf nodes.

Let $H_m$ denote a marked complete binary tree of depth $m$ , where non-leaf nodes are marked with features $f_1,\cdots ,f_{2^m-1}$ , and the leaves are marked with integers 1 through $2^m$ . Each non-leaf node has two leaving edges, marked with 0 and 1. For each $j=1,\cdots ,2^m$ , we define a DR $r_j$ as follows. Consider a full path in $H_m$ from the root to the leaf marked $j$ , represented as $v_0,d_0,\cdots ,v_{m-1},d_{m-1},v_m$ , where for every $i=0,\cdots ,m-1$ , the node $v_i$ marked with $f_{l_i}$ , and the edge $d_i$ is marked with $b_i\in E_2$ . Then the DR $r_j$ is given by:

$\left(f_{l_0}=b_0\right)\wedge \cdots \wedge \left(f_{l_{m-1}}=b_{m-1}\right)\to j.$

We define $S_m$ as the set of DRs $r_1,\cdots ,r_{2^m}$ . It follows that $n\left(S_m\right)=2^m-1$ and $V\left(S_m\right)=2$ .

We examine the task $T\left({\phi }_{AAR},S_m,2\right)$ and prove that $h^d\left({\phi }_{AAR},S_m,2\right)\le m$ . To this end, we convert the tree $H_m$ into a DDT, denoted by $K_m$ , that corresponds to the task $T\left({\phi }_{AAR},S_m,2\right)$ . This is done by introducing a new node $v$ and an edge $d$ directed from $v$ to the root of $H_m$ , leaving both $v$ and $d$ unmarked. Each leaf node in $H_m$ previously marked with $j$ (for $j=1,\cdots ,2^m$ ) is now marked with $\left\{r_j\right\}$ . The resulting DDT $K_m$ solves the task $T\left({\phi }_{AAR},S_m,2\right)$ and has a depth of $m$ .

Thus, for every $m\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ , we obtained an example of a DRS $S_m$ satisfying $n\left(S_m\right)=2^m-1$ and $L\left(S_m\right)=m{2}^m$ . Moreover, there exists a DDT $K_m$ that solves the task $T\left({\phi }_{AAR},S_m,2\right)$ , having depth exactly $m$ and number of nodes is $2^{m+1}$ nodes.

We now turn to the second sequence of DRSs. Let $m\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ . Define $Q_m$ as the DRS:

$\left\{\left(f_1=0\right)\to 0,\left(f_1=1\right)\to 1,\cdots ,\left(f_m=0\right)\to 0,\left(f_m=1\right)\to 1\right\}.$

Clearly, $V\left(Q_m\right)=2$ . Consider the task $T\left({\phi }_{AAR},Q_m,2\right)$ . It can be shown that for any two distinct tuples $\overline{b},\overline{d}\in E_2^m$ , we have ${\phi }_{AAR}\left(\overline{b}\right)\ne {\phi }_{AAR}\left(\overline{d}\right)$ . As a result, any NDT that solves the task $T\left({\phi }_{AAR},Q_m,2\right)$ must contain at least $2^m$ leaf nodes.

Consequently, for every $m\in {\mathbb{N}}_0\backslash \left\{0,1\right\}$ , we have obtained a DRS $Q_m$ such that $n\left(Q_m\right)=m$ and $L\left(Q_m\right)=2m$ . Furthermore, any decision tree, whether deterministic or nondeterministic, that solves the task $T\left({\phi }_{AAR},S_m,2\right)$ must contain at least $2^m$ nodes.

4. Comparative analysis of DDTs (Deterministic Decision Trees) and NDTs (Nondeterministic Decision Trees)

This section focuses on analyzing the minimum depths of DDTs and NDTs that solve the task $T\left(\phi ,S,k\right)$ .

Theorem 1 Suppose $S$ be a DRS, $k\ge V\left(S\right)$ , and $\phi$ be a solution map for the pair $\left(S,k\right)$ . Then

$h^a\left(\phi ,S,k\right)\le h^d\left(\phi ,S,k\right)\le h^a{\left(\phi ,S,k\right)}^2.$

Proof. Since any DDT that solves the task $T\left(\phi ,S,k\right)$ is a NDT that solves the task $T\left(\phi ,S,k\right)$ , so the inequality $h^a\left(\phi ,S,k\right)\le h^d\left(\phi ,S,k\right)$ holds. We now show that $h^d\left(\phi ,S,k\right)\le h^a{\left(\phi ,S,k\right)}^2$ .

Let $n\left(S\right)=n$ and let, for definiteness, $F\left(S\right)=\left\{f_1,\cdots ,f_n\right\}$ . Let $\mathcal{G}$ be a NDT over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ , where $h\left(\mathcal{G}\right)=h^a\left(\phi ,S,k\right)$ . Let $F{P}^{+}\left(\mathcal{G}\right)$ denote the set of full paths $$ from $FP\left(\mathcal{G}\right)$ for which the corresponding equation system is consistent. We assign a number from ${\mathbb{N}}_0$ to each path in $F{P}^{+}\left(\mathcal{G}\right)$ to ensure all paths are distinctly identified. Two full paths are said to be equivalent if . This equivalence relation partitions $F{P}^{+}\left(\mathcal{G}\right)$ into equivalence classes $C_1,\cdots ,C_t$ .

We now prove that for any two full paths are not equivalent, then the system $K\left(1_{}\right)\cup K\left(2_{}\right)$ is inconsistent. Suppose, for contradiction, that is consistent. Then there exists a tuple $\overline{d}\in E_k^n$ such that $K\left(1_{}\right)\subseteq K\left(S,\overline{d}\right)$ and $K\left(2_{}\right)\subseteq K\left(S,\overline{d}\right)$ . This implies that both paths accept $\overline{d}$ , which leads to a contradiction because $\tau \left(1_{}\right)\ne \tau \left(2_{}\right)$ .

Suppose $\overline{b}=\left(b_1,\cdots ,b_n\right)\in E_k^n$ . Let us describe the behavior of a DDT $G$ with respect to the tuple $\overline{b}$ , where $G$ solves the task $T\left(\phi ,S,k\right)$ . As a consequence, we derive the description of a full path $\rho \left(\overline{b}\right)$ in the DT $G$ that accepts the tuple $\overline{b}$ . The set of full paths of the DT $G$ coincides with the set $\left\{\rho \left(\overline{b}\right):\overline{b}\in E_k^n\right\}$ .

Step 1:

Initialize $\text{Ξ}:=F{P}^{+}\left(\mathcal{G}\right)$ . For every path $\in F{P}^{+}\left(\mathcal{G}\right)$ , define . Proceed to Step 2.

Step 2:

This step is divided into three phases:

(a) If there exists a full path $\in \text{Ξ}$ such that is empty, then the DT $G$ terminates and returns the solution $\tau \left(\rho \left(\overline{b}\right)\right)=\tau \left(\right)$ , which will be attached to the leaf node of the path $\rho \left(\overline{b}\right)$ . Otherwise, proceed to (b).

(b) Set $i_0$ the minimum index $i$ in $\left\{1,\cdots ,t\right\}$ such that $C_i\cap \text{Ξ}\ne \varnothing$ . Choose a full path with the minimum number. If $C_{i_0}\cap \text{Ξ}=\text{Ξ}$ , then the tree $G$ terminates and returns the solution , which will be attached to the leaf node of the path $\rho \left(\overline{b}\right)$ . Otherwise, proceed to (c).

(c) Let $\left\{f_{i_1},\cdots ,f_{i_m}\right\}$ be all features from the equations containing in . The DT $G$ computes values of these features and obtains the set of equations $K=\left\{f_{i_1}=b_{i_1},\cdots ,f_{i_m}=b_{i_m}\right\}$ . Then, for every full path : if is inconsistent, then set , otherwise, set . Proceed to Step 2.

We observe that for the full path $\rho \left(\overline{b}\right)$ , we have $K\left(\rho \left(\overline{b}\right)\right)\subseteq K\left(S,\overline{b}\right)$ , meaning that this path accepts the tuple $\overline{b}$ . We now show that the solution $\tau \left(\rho \left(\overline{b}\right)\right)$ , which is attached to the leaf node of this path, is derivable from $K\left(\rho \left(\overline{b}\right)\right)$ . The two variants of the finishing the work of the DT $G$ are described in phases (a) and (b) of Step 2.

(a) There exists a full path such that $Q\left(\right)$ is empty. In this situation, the DT $G$ terminates and returns the solution $\tau \left(\rho \left(\overline{b}\right)\right)=\tau \left(\right)$ , which will be attached to the leaf node of the path $\rho \left(\overline{b}\right)$ . Clearly, we have . Since is derivable from $K\left(\right)$ , it follows that is derivable from $K\left(\rho \left(\overline{b}\right)\right)$ .

(b) There is no any full path such that is empty and there is $i_0\in \left\{1,\cdots ,t\right\}$ for which $C_{i_0}\cap \text{Ξ}\ne \varnothing$ and $C_{i_0}\cap \text{Ξ}=\text{Ξ}$ . Let us select the path with the minimum number. In this case, the DT $G$ terminates and returns the solution , which will be attached to the leaf node of the path $\rho \left(\overline{b}\right)$ .

Since $\mathcal{G}$ solves the task $T\left(\phi ,S,k\right)$ , there exists a full path $\zeta \in F{P}^{+}\left(\mathcal{G}\right)$ that accepts the tuple $\overline{b}$ . For this path, we have $K\left(\zeta \right)\subseteq K\left(S,\overline{b}\right)$ and $\tau \left(\zeta \right)=\phi \left(\overline{b}\right)$ . Given that $K\left(\rho \left(\overline{b}\right)\right)\subseteq K\left(S,\overline{b}\right)$ , the path $\zeta$ belongs to $\text{Ξ}$ and consequently, belongs to $C_{i_0}$ . Hence, leaf nodes of the paths from $C_{i_0}$ are marked with the solution $\phi \left(\overline{b}\right)$ . In particular, this implies .

Let us now prove that is derivable from $K\left(\rho \left(\overline{b}\right)\right)$ . Assume the contrary, that it is not derivable. Then there exists a tuple $\overline{d}\in E_k^n$ , which is accepted by the path $\rho \left(\overline{b}\right)$ and for which $\phi \left(\overline{d}\right)\ne \phi \left(\overline{b}\right)$ . Since $\mathcal{G}$ solves the task $T\left(\phi ,S,k\right)$ , there is a full path $\theta \in F{P}^{+}\left(\mathcal{G}\right)$ that accepts the tuple $\overline{d}$ . For this path, $K\left(\theta \right)\subseteq K\left(S,\overline{d}\right)$ and $\tau \left(\theta \right)=\phi \left(\overline{d}\right)$ . Since $K\left(\rho \left(\overline{b}\right)\right)\subseteq K\left(S,\overline{d}\right)$ , the path $\theta$ belongs to the set $\text{Ξ}$ and therefore, to the set $C_{i_0}$ , but this is impossible since leaf nodes of all paths from $C_{i_0}$ are marked with the solution $\phi \left(\overline{b}\right)$ and $\phi \left(\overline{d}\right)\ne \phi \left(\overline{b}\right)$ .

Therefore, we obtain that the DT $G$ solves the task $T\left(\phi ,S,k\right)$ .

It is clear that in each full iteration of Step 2, including phase (c), the DT $G$ evaluates at most $h\left(\mathcal{G}\right)$ feature values. We now prove that the number of such full iterations of Step 2 is at most $h\left(\mathcal{G}\right)$ .

Since for any non-equivalent paths the equation system is inconsistent, it follows that during each full iteration of Step 2, every path not in $C{i}_0$ (i.e., in $\text{Ξ}\backslash C{i}_0$ ) will either be removed from $\text{Ξ}$ or will have the cardinality of decreased by at least 1. Evidently, for each full paths , the cardinality of the set is at most $h\left(\mathcal{G}\right)$ . Therefore, after $h\left(\mathcal{G}\right)$ complete repetitions of Step 2, we will find a full path for which the set is empty or we will have $\text{Ξ}=\text{Ξ}\cap C_{i_0}$ . In both cases, the DT $G$ will finish its work.

Hence, the number of internal nodes along the path $\rho \left(\overline{b}\right)$ in $G$ is at most $h{\left(\mathcal{G}\right)}^2$ . Taking into account that we considered an arbitrary full path in the DT $G$ and $h\left(\mathcal{G}\right)=h^a\left(\phi ,S,k\right)$ , we obtain $h\left(G\right)\le h^a{\left(\phi ,S,k\right)}^2$ . Since $G$ is a DDT over $T\left(\phi ,S,k\right)$ that solves the task $T\left(\phi ,S,k\right)$ , we have $h^d\left(\phi ,S,k\right)\le h^a{\left(\phi ,S,k\right)}^2$ . □

5. A Greedy Approach to Modeling the Operation of DDT (Deterministic Decision Tree)

Consider a DRS $S$ with $n\left(S\right)=n$ , and $k\ge V\left(S\right)$ . We define $ES\left(S,k\right)$ as the set containing equation systems of the form

$\left\{f_{i_1}=b_1,\cdots ,f_{i_m}=b_m\right\},$

where $m\in {\mathbb{N}}_0$ , $f_{i_1},\cdots ,f_{i_m}\in F\left(S\right)$ , and $b_1,\cdots ,b_m\in E_k$ . We denote by $E{S}^{+}\left(S,k\right)$ the set of consistent equation systems from $ES\left(S,k\right)$ . For $\alpha \in E{S}^{+}\left(S,k\right)$ , denote $E_k^n\left(\alpha \right)=\left\{\overline{b}\in E_k^n:\alpha \subseteq K\left(S,\overline{b}\right)\right\}$ . This set can be interpreted as the set of solutions from $E_k^n$ of the equation system $\alpha$ .

Definition 12 Let $\phi$ be a solution map for the pair $\left(S,k\right)$ and $\alpha \in E{S}^{+}\left(S,k\right)$ . Let us define the parameter $M_{\alpha }\left(\phi ,S,k\right)$ . For any $\overline{b}\in E_k^n$ , we denote by $M_{\alpha }\left(\phi ,S,k,\overline{b}\right)$ the minimum number $m\in {\mathbb{N}}_0$ such that there exists a subsystem $\beta$ of the equation system $K\left(S,\overline{b}\right)$ , which contains $m$ equations and for which the map $\phi$ is constant on the set $E_k^n\left(\alpha \cup \beta \right)$ . Then $M_{\alpha }\left(\phi ,S,k\right)=max\left\{M_{\alpha }\left(\phi ,S,k,\overline{b}\right):\overline{b}\in E_k^n\right\}$ . Note that $M_{\varnothing }\left(\phi ,S,k\right)=0$ if and only if $\phi$ is a degenerate map.

A related parameter was introduced for decision tables within test theory in [20]. In the concept classes of exact learning, a similar parameter proposed in [21], where it is known as the extended teaching dimension, generalizes the teaching dimension concept from [22].

We will prove two statements related to the parameter $M_{\alpha }\left(\phi ,S,k\right)$ . The first one has some independent interest.

Lemma 2 Suppose $S$ be a DRS, $k\ge V\left(S\right)$ , and $\phi$ be a solution map for the pair $\left(S,k\right)$ . Then

$M_{\varnothing }\left(\phi ,S,k\right)=h^a\left(\phi ,S,k\right).$

Proof. Let $n\left(S\right)=n$ , $\mathcal{G}$ be a NDT over $T\left(\phi ,S,k\right)$ , which solves the task $T\left(\phi ,S,k\right)$ , where $h\left(\mathcal{G}\right)=h^a\left(\phi ,S,k\right)$ , and $\overline{b}$ be a tuple from $E_k^n$ for which $M_{\varnothing }\left(\phi ,S,k\right)=M_{\varnothing }\left(\phi ,S,k,\overline{b}\right)$ . Since $\mathcal{G}$ solves the task $T\left(\phi ,S,k\right)$ , there is a path , where and, for any tuple , . Hence, is a subsystem of $K\left(S,\overline{b}\right)$ where the map $\phi$ is constant on the set . Therefore, there are at most $h\left(\mathcal{G}\right)$ equations in . As a result, $M_{\varnothing }\left(\phi ,S,k\right)=M_{\varnothing }\left(\phi ,S,k,\overline{b}\right)\le h\left(\mathcal{G}\right)=h^a\left(\phi ,S,k\right)$ , i.e, $M_{\varnothing }\left(\phi ,S,k\right)\le h^a\left(\phi ,S,k\right)$ .

We now show that $h^a\left(\phi ,S,k\right)\le M_{\varnothing }\left(\phi ,S,k\right)$ . Let $\overline{b}\in E_k^n$ . From the definition of the parameter $M_{\varnothing }\left(\phi ,S,k\right)$ , there exists a subsystem $\alpha \left(\overline{b}\right)$ of $K\left(S,\overline{b}\right)$ , that contains at most $M_{\varnothing }\left(\phi ,S,k\right)$ equations and the map $\phi$ is equal to some constant $s\left(\overline{b}\right)$ on the set $E_k^n\left(\alpha \left(\overline{b}\right)\right)$ . It is not difficult to build a full path having at most $M_{\varnothing }\left(\phi ,S,k\right)$ internal nodes, for which and equals $s\left(\overline{b}\right)$ . We identify roots of the full paths , $\overline{b}\in E_k^n$ , and denote the resulting DT by $\mathcal{G}$ . It can be shown that $\mathcal{G}$ is a NDT over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ , where $h\left(\mathcal{G}\right)\le M_{\varnothing }\left(\phi ,S,k\right)$ . Therefore $h^a\left(\phi ,S,k\right)\le M_{\varnothing }\left(\phi ,S,k\right)$ . Thus, $M_{\varnothing }\left(\phi ,S,k\right)=h^a\left(\phi ,S,k\right)$ . □

Lemma 3 Consider a DRS, $k\ge V\left(S\right)$ , $\alpha \in E{S}^{+}\left(S,k\right)$ , and $\phi$ be a solution map for the pair $\left(S,k\right)$ . Then

$M_{\varnothing }\left(\phi ,S,k\right)\ge M_{\alpha }\left(\phi ,S,k\right).$

Proof. Let $n\left(S\right)=n$ , $\overline{b}\in E_k^n$ and $\beta$ be a subsystem of $K\left(S,\overline{b}\right)$ , where the map $\phi$ is constant on the set $E_k^n\left(\beta \right)$ . Then $\beta$ is a subsystem of $K\left(S,\overline{b}\right)$ , where the map $\phi$ is constant on the set $E_k^n\left(\alpha \cup \beta \right)$ . From here it follows that $M_{\varnothing }\left(\phi ,S,k,\overline{b}\right)\ge M_{\alpha }\left(\phi ,S,k,\overline{b}\right)$ . Since $\overline{b}$ is an arbitrary tuple from the set $E_k^n$ , we obtain $M_{\varnothing }\left(\phi ,S,k\right)\ge M_{\alpha }\left(\phi ,S,k\right)$ . □

Definition 13 Consider a DRS $S$ , $k\ge V\left(S\right)$ , and $\phi$ be a solution map for the pair $\left(S,k\right)$ . An uncertainty measure for the triple $\left(\phi ,S,k\right)$ is a function $\gamma :E{S}^{+}\left(S,k\right)\to {\mathbb{N}}_0$ , which satisfies the following conditions:

• For any $\alpha \in E{S}^{+}\left(S,k\right)$ , $\gamma \left(\alpha \right)=0$ if and only if the map $\phi$ is constant on the set $E_k^n\left(\alpha \right)$ .

• Let $\alpha \cup \left\{f_i=b\right\}\in E{S}^{+}\left(S,k\right)$ and the equation $f_i=b$ do not belong to the system $\alpha$ . Then $\gamma (\varnothing )-\gamma \left(\left\{f_i=b\right\}\right)\ge \gamma \left(\alpha \right)-\gamma \left(\alpha \cup \left\{f_i=b\right\}\right)$

Note that $\gamma (\varnothing )=0$ if and only if the map $\phi$ is degenerate. We proceed by proving an auxiliary statement.

Lemma 4 Consider a DRS $S$ , $k\ge V\left(S\right)$ , $\phi$ be a nondegenerate solution map for the pair $\left(S,k\right)$ , and $\gamma$ be an uncertainty measure for the triple $\left(\phi ,S,k\right)$ . Let $n\left(S\right)=n$ , $F\left(S\right)=\left\{f_1,\cdots ,f_n\right\}$ , $\alpha \in E{S}^{+}\left(S,k\right)$ and $\gamma \left(\alpha \right)>0$ . Let, for $i=1,\cdots ,n$ , $d_i$ be a number from $E_k$ such that $\gamma \left(\alpha \cup \left\{f_i=d_i\right\}\right)=max\left\{\gamma \left(\alpha \cup \left\{f_i=d\right\}\right):d\in E_k\right\}$ , and $t$ be the minimum $i\in \left\{1,\cdots ,n\right\}$ for which $\gamma \left(\alpha \cup \left\{f_i=d_i\right\}\right)$ has the minimum value. Then

$\gamma \left(\alpha \cup \left\{f_t=d_t\right\}\right)\le \gamma \left(\alpha \right)\left(1-1/M_{\alpha }\left(\phi ,S,k\right)\right).$

Proof. By the definition of the parameter $M_{\alpha }\left(\phi ,S,k\right)$ and from $\gamma \left(\alpha \right)>0$ , we conclude that there exist pairwise distinct features $f_{i_1},\cdots ,f_{i_m}\in \left\{f_1,\cdots ,f_n\right\}$ such that $\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_m}=d_{i_m}\right\}\right)=0$ and $1\le m\le M_{\alpha }\left(\phi ,S,k\right)$ . Then

$\begin{array}{l}\gamma \left(\alpha \right)-\left(\gamma \left(\alpha \right)-\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1}\right\}\right)\right)\\ -\left(\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1}\right\}\right)-\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},f_{i_2}=d_{i_2}\right\}\right)\right)-\cdots \\ -\left(\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_{m-1}}=d_{i_{m-1}}\right\}\right)-\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_m}=d_{i_m}\right\}\right)\right)\\ =\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_m}=d_{i_m}\right\}\right)=0.\end{array}$

Since the features $f_{i_1},\cdots ,f_{i_m}$ are pairwise different, for $j=1,\cdots ,m-1$ , the equation system $\left\{f_{i_1}=d_{i_1},\cdots ,f_{i_{j+1}}=d_{i_{j+1}}\right\}$ is consistent and the equation $f_{i_{j+1}}=d_{i_{j+1}}$ does not belong to the equation system $\left\{f_{i_1}=d_{i_1},\cdots ,f_{i_j}=d_{i_j}\right\}$ . Using the definition of uncertainty measure $\gamma$ , we obtain that, for $j=1,\cdots ,m-1$ ,

$\begin{array}{l}\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_j}=d_{i_j}\right\}\right)-\gamma \left(\alpha \cup \left\{f_{i_1}=d_{i_1},\cdots ,f_{i_j}=d_{i_j},f_{i_{j+1}}=d_{i_{j+1}}\right\}\right)\\ \le \gamma \left(\alpha \right)-\gamma \left(\alpha \cup \left\{f_{i_{j+1}}=d_{i_{j+1}}\right\}\right).\end{array}$

Therefore $\gamma \left(\alpha \right)-{\displaystyle {\sum }_{j=1}^m\left(\gamma \left(\alpha \right)-\gamma \left(\alpha \cup \left\{f_{i_j}=d_{i_j}\right\}\right)\right)}\le 0$ . Since

$\gamma \left(\alpha \cup \left\{f_t=d_t\right\}\right)\le \gamma \left(\alpha \cup \left\{f_{i_j}=d_{i_j}\right\}\right)$ for $j=1,\cdots ,m$ , we have $\gamma \left(\alpha \right)-m\left(\gamma \left(\alpha \right)-\gamma \left(\alpha \cup \left\{f_t=d_t\right\}\right)\right)\le 0$ and $\gamma \left(\alpha \cup \left\{f_t=d_t\right\}\right)\le \gamma \left(\alpha \right)\left(1-1/m\right)$ . Given that $m\le M_{\alpha }\left(\phi ,S,k\right)$ , it follows that $\gamma \left(\alpha \cup \left\{f_t=d_t\right\}\right)\le \gamma \left(\alpha \right)\left(1-1/M_{\alpha }\left(\phi ,S,k\right)\right)$ . □

Let $S$ be a DRS with $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , $\phi$ be a nondegenerate solution map for the pair $\left(S,k\right)$ , and $\gamma$ be an uncertainty measure for the triple $\left(\phi ,S,k\right)$ . We now consider an algorithm $\mathcal{U}$ that, for the DRS $S$ , the number $k$ , the solution map $\phi$ , the uncertainty measure $\gamma$ , and a tuple $\overline{b}=\left(b_1,\cdots ,b_n\right)\in E_k^n$ , simulates the work of a DDT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ . Therefore, we get the description of a full path $\rho \left(\overline{b}\right)$ from the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ which accepts the tuple $\overline{b}$ . The set of full paths of the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ coincides with the set $\left\{\rho \left(\overline{b}\right):\overline{b}\in E_k^n\right\}$ . Let, for definiteness, $F\left(S\right)=\left\{f_1,\cdots ,f_n\right\}$ .

Algorithm $\mathcal{U}$

Step 1:

Set $j:=1$ and $\alpha :=\varnothing$ . Proceed to Step 2.

Step 2:

If $\gamma \left(\alpha \right)=0$ , then the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ terminates and returns the solution $\tau \left(\rho \left(\overline{b}\right)\right)=\phi \left(\overline{d}\right)$ , where $\overline{d}$ is an arbitrary tuple from the set $E_k^n\left(\alpha \right)$ . This solution is attached to the leaf node of the full path $\rho \left(\overline{b}\right)$ . Otherwise, proceed to Step 3.

Step 3:

Set $t_j$ the minimum $i\in \left\{1,\cdots ,n\right\}$ for which $\text{max}\left\{\gamma \left(\alpha \cup \left\{f_i=d\right\}\right):d\in E_k\right\}$ has the minimum value. Compute the value of the feature $f_{t_j}$ . Set $\alpha :=\alpha \cup \left\{f_{t_j}=b_{t_j}\right\}$ and $j:=j+1$ . Proceed to Step 2.

Theorem 5 Let $S$ be a DRS with $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , $\phi$ be a nondegenerate solution map for the pair $\left(S,k\right)$ , and $\gamma$ be an uncertainty measure for the triple $\left(\phi ,S,k\right)$ . Then $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ is a DDT over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ such that

$h\left(G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)\right)\le M_{\varnothing }\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1.$

Proof. Let, for definiteness, $F\left(S\right)=\left\{f_1,\cdots ,f_n\right\}$ . Consider an arbitrary tuple $\overline{b}=\left(b_1,\cdots ,b_n\right)\in E_k^n$ . The algorithm $\mathcal{U}$ constructs the full path $\rho \left(\overline{b}\right)$ within the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ , that accepts this tuple. It is not difficult to show that the solution $\tau \left(\rho \left(\overline{b}\right)\right)$ is derivable from $K\left(\rho \left(\overline{b}\right)\right)$ . Since $\rho \left(\overline{b}\right)$ is an arbitrary full path in the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ , it follows that this tree is a DDT over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ .

We now analyze the number of internal nodes along the path $\rho \left(\overline{b}\right)$ . Suppose Step 3 of algorithm $\mathcal{U}$ is repeated $p$ times during its work. Then $\rho \left(\overline{b}\right)=v_0,d_0,v_1,d_1,\cdots ,v_p,d_p,v_{p+1}$ , where $v_0$ is the root of DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ , $v_{p+1}$ is a leaf node and, for $j=0,\cdots ,p$ , the edge $d_j$ leaves the node $v_j$ and enters the node $v_{j+1}$ . The node $v_0$ and the edge $d_0$ are not marked. For $j=1,\cdots ,p$ , the node $v_j$ is marked with the feature $f_{t_j}$ and the edge $d_j$ is marked with $b_{t_j}$ . The leaf node $v_{p+1}$ is marked with $\tau \left(\rho \left(\overline{b}\right)\right)$ . Since the map $\phi$ is nondegenerate, $\gamma (\varnothing )\ge 1$ and $p\ge 1$ . We now show that $p\le M_{\varnothing }\left(\phi ,S,k\right)\text{ln}\gamma (\varnothing )+1$ .

For $j=1,\cdots ,p$ , let ${\alpha }_j=\left\{f_{t_1}=b_{t_1},\cdots ,f_{t_j}=b_{t_j}\right\}$ . Denote ${\alpha }_0=\varnothing$ . It is clear that, for $j=0,\cdots ,p$ , the equation system ${\alpha }_j$ is consistent. From the description of the algorithm $\mathcal{U}$ it follows that, for $j=0,\cdots ,p-1$ , $\gamma \left({\alpha }_j\right)>0$ . By Lemma 4, for $j=0,\cdots ,p-1$ , $\gamma \left({\alpha }_{j+1}\right)\le \gamma \left({\alpha }_j\right)\left(1-1/M_{{\alpha }_j}\left(\phi ,S,k\right)\right)$ . From Lemma 3, we get that, for $j=0,\cdots ,p-1$ ,

$M_{{\alpha }_j}\left(\phi ,S,k\right)\le M_{\varnothing }\left(\phi ,S,k\right).$

Therefore, for $j=0,\cdots ,p-1$ , $\gamma \left({\alpha }_{j+1}\right)\le$ $\gamma \left({\alpha }_j\right)\left(1-1/M_{\varnothing }\left(\phi ,S,k\right)\right)$ .

Since the map $\phi$ is nondegenerate, $M_{\varnothing }\left(\phi ,S,k\right)\ge 1$ . Let $M_{\varnothing }\left(\phi ,S,k\right)=1$ . Then $\gamma \left({\alpha }_1\right)\le 0$ , i.e., $p=1$ . In this case, $p\le M_{\varnothing }\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1$ .

Let us assume now that $M_{\varnothing }\left(\phi ,S,k\right)\ge 2$ . In this case, $\gamma \left({\alpha }_{p-1}\right)\le \gamma (\varnothing ){\left(1-1/M_{\varnothing }\left(\phi ,S,k\right)\right)}^{p-1}$ . From the description of algorithm $\mathcal{U}$ , it follows that $\gamma \left({\alpha }_{p-1}\right)\ge 1$ . Thus, $1\le \gamma (\varnothing ){\left(1-1/M_{\varnothing }\left(\phi ,S,k\right)\right)}^{p-1}$ , ${\left(M_{\varnothing }\left(\phi ,S,k\right)/\left(M_{\varnothing }\left(\phi ,S,k\right)-1\right)\right)}^{p-1}\le \gamma (\varnothing )$ and ${\left(1+1/\left(M_{\varnothing }\left(\phi ,S,k\right)-1\right)\right)}^{p-1}\le \gamma (\varnothing )$ . By taking the natural logarithm on both sides of the inequality, we get $\left(p-1\right)\ln \left(1+1/\left(M_{\varnothing }\left(\phi ,S,k\right)-1\right)\right)\le \ln L\left(S\right)$ . It is well-known fact that, the inequality $\text{ln}\left(1+1/q\right)>1/\left(q+1\right)$ holds, for any natural $q$ . Given that $M_{\varnothing }\left(\phi ,S,k\right)\ge 2$ , it follows that $\left(p-1\right)/M_{\varnothing }\left(\phi ,S,k\right)<\ln \gamma (\varnothing )$ and $p<M_{\varnothing }\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1$ . Since $\rho \left(\overline{b}\right)$ is an arbitrary full path in the DT $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ , we conclude that $h\left(G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)\right)\le M_{\varnothing }\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1$ . □

From Lemma 2 and Theorem 1, we can conclude the statement below.

Corollary 1 Let $S$ be a DRS with $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , $\phi$ be a nondegenerate solution map for the pair $\left(S,k\right)$ , and $\gamma$ be an uncertainty measure for the triple $\left(\phi ,S,k\right)$ . Then $G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)$ is a DDT over $T\left(\phi ,S,k\right)$ , that solves the task $T\left(\phi ,S,k\right)$ such that

$h\left(G_{\mathcal{U}}\left(\phi ,S,k,\gamma \right)\right)\le h^a\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1\le h^d\left(\phi ,S,k\right)\ln \gamma (\varnothing )+1.$

In order to consider the work of algorithm $\mathcal{U}$ efficient, we need to have

• An efficient algorithm that finds the value $\phi \left(\overline{d}\right)$ for a given tuple $\overline{d}\in E_k^n$ . In this case, we have direct access to the tuple $\overline{d}$ and we do not need to compute values of the features from the set $F\left(S\right)$ .

• An efficient algorithm that finds the value $\gamma \left(\alpha \right)$ for a given equation system $\alpha \in E{S}^{+}\left(S,k\right)$ .

We find it difficult to study the complexity of algorithms for computing individual functions $\phi$ and $\gamma$ with finite domains. We defer a detailed discussion of this issue to the next section, in which we study infinite parametric families of functions $\phi$ and $\gamma$ .

6. Recognition of Applicable Special Sets of Rules

Let $S$ be a DRS with $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , and $W$ be a nonempty set of nonempty subsets of $S$ such that, for any $w\in W$ , the set of equations $K\left(w\right)={\displaystyle {\cup }_{r\in w}K\left(r\right)}$ is consistent. We will call subsets $w$ from $W$ special subsets of $S$ and will interpret them as subsets of $S$ of special interest. We will call the set $W$ a family of special subsets for the DRS $S$ .

Let $\overline{b}\in E_k^n$ . We will say that a special subset $w$ is applicable for the tuple $\overline{b}$ if each DR $r\in w$ is applicable for this tuple, i.e., if $K\left(w\right)\subseteq K\left(S,\overline{b}\right)$ . Let us define a solution map ${\phi }_W$ for the pair $\left(S,k\right)$ as follows: for $\overline{b}\in E_k^n$ , ${\phi }_W\left(\overline{b}\right)$ is the set of all special subsets from $W$ that are applicable for the tuple $\overline{b}$ . It is clear that the solution map ${\phi }_W$ is nondegenerate. In this section, we will study the task $T\left({\phi }_W,S,k\right)$ . Let us consider two examples:

• $W_1=\left\{\left\{r\right\}:r\in S\right\}$ . The task $T\left({\phi }_{W_1},S,k\right)$ coincides with the task All Applicable Rules.

• $W_2$ is the set of all subsets of $S$ of the kind $\left\{r_1,r_2\right\}$ , where $r_1$ and $r_2$ have different decisions and $K\left(r_1\right)\cup K\left(r_2\right)$ is consistent. If the set $W_2$ is nonempty, then it is a family of special subsets for the DRS $S$ .

Let us define an uncertainty measure ${\gamma }_W$ for the triple $\left({\phi }_W,S,k\right)$ . Let $\alpha \in E{S}^{+}\left(S,k\right)$ . For each subset $w\in W$ , we consider two parameters: $p_{\alpha }\left(w\right)=\left|K\left(w\right)\backslash \alpha \right|$ and $q_{\alpha }\left(w\right)$ that is equal to 1 if the equation system $K\left(w\right)\cup \alpha$ is consistent and to 0 otherwise. Denote ${\pi }_{\alpha }\left(w\right)=p_{\alpha }\left(w\right)q_{\alpha }\left(w\right)$ and ${\gamma }_W\left(\alpha \right)={\displaystyle {\sum }_{w\in W}{\pi }_{\alpha }\left(w\right)}$ .

Proposition 6 Let $S$ be a DRS with $n\left(S\right)=n$ , $k\ge V\left(S\right)$ , and $W$ be a family of special subsets for the DRS $S$ . Then ${\gamma }_W$ is an uncertainty measure for the triple $\left({\phi }_W,S,k\right)$ .

Proof. (a) First, we show that, for any $\alpha \in E{S}^{+}\left(S,k\right)$ , ${\gamma }_W\left(\alpha \right)=0$ if and only if the map ${\phi }_W$ is constant on the set $E_k^n\left(\alpha \right)$ . Let ${\gamma }_W\left(\alpha \right)=0$ . Then, for any $w\in W$ , ${\pi }_{\alpha }\left(w\right)=0$ . Let us consider an arbitrary $w\in W$ . Since ${\pi }_{\alpha }\left(w\right)=0$ , either $p_{\alpha }\left(w\right)=0$ or $q_{\alpha }\left(w\right)=0$ (obviously, the equalities $p_{\alpha }\left(w\right)=0$ and $q_{\alpha }\left(w\right)=0$ cannot be fulfilled simultaneously). If $p_{\alpha }\left(w\right)=0$ , then, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ is applicable for $\overline{b}$ . If $q_{\alpha }\left(w\right)=0$ , then, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ is not applicable for $\overline{b}$ . From here it follows that the map ${\phi }_W$ is constant on the set $E_k^n\left(\alpha \right)$ .

Let the map ${\phi }_W$ be constant on the set $E_k^n\left(\alpha \right)$ . Let us consider an arbitrary subset $w\in W$ . Then either, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ is applicable for $\overline{b}$ or, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ is not applicable for $\overline{b}$ . Let, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ be applicable for $\overline{b}$ . Then $K\left(w\right)\subseteq \alpha$ and $p_{\alpha }\left(w\right)=0$ . Let, for any $\overline{b}\in E_k^n\left(\alpha \right)$ , the subset of DRs $w$ be not applicable for $\overline{b}$ . Then the equation system $K\left(w\right)\cup \alpha$ is inconsistent and $q_{\alpha }\left(w\right)=0$ . Thus, ${\pi }_{\alpha }\left(w\right)=0$ . Since $w$ is an arbitrary subset of the set $W$ , we obtain ${\gamma }_W\left(\alpha \right)=0$ .

(b) We now show that, for any $\alpha \cup \left\{f_i=b\right\}\in E{S}^{+}\left(S,k\right)$ , if $\left\{f_i=b\right\}$ is not a subset of $\alpha$ , then

${\gamma }_W(\varnothing )-{\gamma }_W\left(\left\{f_i=b\right\}\right)\ge {\gamma }_W\left(\alpha \right)-{\gamma }_W\left(\alpha \cup \left\{f_i=b\right\}\right).$ (1)

We denote by $\beta$ the equation system $\left\{f_i=b\right\}$ . To prove (1), it is enough to show that, for any $w\in W$ , the following inequality holds:

${\pi }_{\varnothing }\left(w\right)-{\pi }_{\beta }\left(w\right)\ge {\pi }_{\alpha }\left(w\right)-{\pi }_{\alpha \cup \beta }\left(w\right).$ (2)

It is easy to see that $p_{\varnothing }\left(w\right)\ge p_{\alpha }\left(w\right)$ and $q_{\varnothing }\left(w\right)\ge q_{\alpha }\left(w\right)$ . Therefore

${\pi }_{\varnothing }\left(w\right)\ge {\pi }_{\alpha }\left(w\right).$ (3)

We now consider a number of cases.

(i) Let the equation system $K\left(w\right)\cup \beta$ be inconsistent. In this case, ${\pi }_{\beta }\left(w\right)={\pi }_{\alpha \cup \beta }\left(w\right)=0$ . Using (3), we obtain (2).

(ii) Let the equation system $K\left(w\right)\cup \beta$ be consistent and the equation system $K\left(w\right)\cup \alpha$ be inconsistent. Then ${\pi }_{\alpha }\left(w\right)-{\pi }_{\alpha \cup \beta }\left(w\right)=0$ . It is clear that ${\pi }_{\varnothing }\left(w\right)-{\pi }_{\beta }\left(w\right)\ge 0$ . Therefore (2) holds.

(iii) Let both equation systems $K\left(w\right)\cup \beta$ and $K\left(w\right)\cup \alpha$ be consistent. Since the equation system $\alpha \cup \beta$ is consistent, we obtain that $K\left(w\right)\cup \alpha \cup \beta$ is consistent. In this case, ${\pi }_{\varnothing }\left(w\right)-{\pi }_{\beta }\left(w\right)=p_{\varnothing }\left(w\right)-p_{\beta }\left(w\right)$ and ${\pi }_{\alpha }\left(w\right)-{\pi }_{\alpha \cup \beta }\left(w\right)=p_{\alpha }\left(w\right)-p_{\alpha \cup \beta }\left(w\right)$ . We know that $\beta$ is not a subset of $\alpha$ . Using this fact, it is easy to show that $p_{\varnothing }\left(w\right)-p_{\beta }\left(w\right)=p_{\alpha }\left(w\right)-p_{\alpha \cup \beta }\left(w\right)$ . Therefore (2) holds. □

Suppose $S$ be a DRS, $k\ge V\left(S\right)$ , and $W$ be a family of special subsets for the DRS $S$ . First, we evaluate the depth of the DT $G_{\mathcal{U}}\left({\phi }_W,S,k,{\gamma }_W\right)$ . According to Corollary 1, it is at most $h^a\left({\phi }_W,S,k\right)\ln {\gamma }_W(\varnothing )+1$ . It is clear that ${\gamma }_W(\varnothing )\le \left|W\right|n\left(S\right)$ . Therefore

$h\left(G_{\mathcal{U}}\left({\phi }_W,S,k,{\gamma }_W\right)\right)\le h^a\left({\phi }_W,S,k\right)\left(\ln \left|W\right|+\ln n\left(S\right)\right)+1.$

We now discuss the complexity of the algorithm $\mathcal{U}$ when it generates a full path in the DT $G_{\mathcal{U}}\left({\phi }_W,S,k,{\gamma }_W\right)$ .

The DRS $S$ can be represented by a word over the alphabet $\left\{(,),f,=,\wedge ,\to ,0,1,;\right\}$ in which numbers from ${\mathbb{N}}_0$ (feature indices, feature values, and decisions of the DRs) are in binary representation (are represented by words over the alphabet $\left\{0,1\right\}$ ) and the symbol “;” is used to separate two DRs. The length of this word will be called the size of the DRS $S$ and will be denoted $size\left(S\right)$ . This word defines an order on the set $S$ , that is, all DRs from $S$ are numbered with indices $1,\cdots ,\left|S\right|$ . Each subset $w\in W$ is represented by the set of indices of DRs belonging to it. The set $W$ can be represented by a word over the alphabet $\left\{\{,\},0,1,;\right\}$ in which numbers from ${\mathbb{N}}_0$ (indices of the DRs) are in binary representation and the symbol “;” is used to separate two indices. The length of this word will be called the size of the family $W$ and will be denoted $size\left(W\right)$ .

One can show that there is an algorithm, which finds the value ${\phi }_W\left(\overline{d}\right)$ for a given tuple $\overline{d}\in E_k^{n\left(S\right)}$ and which time complexity is bounded from above by a polynomial depending on $size\left(S\right)$ and $size\left(W\right)$ . One can show also that there is an algorithm, which finds the value ${\gamma }_W\left(\alpha \right)$ for a given equation system $\alpha \in E{S}^{+}\left(S,k\right)$ and which time complexity is bounded from above by a polynomial depending on $size\left(S\right)$ and $size\left(W\right)$ . It is easy to show that $h^a\left({\phi }_W,S,k\right)\le n\left(S\right)$ . Therefore $h\left(G_{\mathcal{U}}\left({\phi }_W,S,k,{\gamma }_W\right)\right)\le n\left(S\right)\left(\ln \left|W\right|+\ln n\left(S\right)\right)+1$ . Using these facts, one can prove that the algorithm $\mathcal{U}$ can be designed to have polynomial time complexity depending on $size\left(S\right)$ and $size\left(W\right)$ .

7. Conclusion

In this paper, various tasks of recognizing the properties of DRSs are investigated. It is proved that the minimum depth of a DDT solving the task is bounded from above by the square of the minimum depth of an NDT. A greedy algorithm for modeling the operation of a DDT on a given tuple of feature values is proposed and investigated. Its complexity is studied for a class of tasks of recognizing the properties of DRSs. A more in-depth theoretical and experimental study of this and similar algorithms is planned in the future.

Acknowledgements

Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST).