Time and Space Complexity of Deterministic and Nondeterministic Decision Trees: Local Approach

Extensive research has been conducted on rough set theory, specifically focusing on the study of decision trees (DTs) and decision rule systems (DRSs). This theory addresses several important questions, including the relationship between DTs and DRSs, the tradeoff between time and space for DTs, and the tradeoff for DRSs.The objective of this paper is to investigate infinite binary information systems (ISs), each consisting of an infinite set (universe) and an infinite set of two-valued functions (features) defined on the universe. We examine the concept of a task within an IS, which is described by a finite number of features and a mapping that assigns a decision to each combination of feature values. Our analysis focuses on deterministic and nondeterministic DTs (DDTs and NDTs) as algorithms for task-solving, with the restriction that only features from the task description are used.NDTs serve as representations of DRSs and can sometimes have lower space complexity compared to the original DRSs. We study the time and space complexity of DTs, specifically examining the depth and the number of nodes in these trees. The obtained results allow us to classify the set of all ISs into three families, enabling the identification of nontrivial relationships between DDTs and DRSs represented by NDTs. For each family, we investigate the tradeoff between time and space for both DDTs and NDTs.

I. Introduction

Extensive research has been dedicated to the examination of decision trees (DTs) and decision rule systems (DRSs) within the field of rough set theory [1] –[6]. The theory focuses, in particular, on the relationship between DTs and DRSs, as well as the tradeoff between time and space associated with both deterministic DTs (DDTs) and DRSs.