@inproceedings{25116dc7633a41a7a7a48bef6ed455b0,
title = "Time and Space Complexity of Deterministic and Nondeterministic Decision Trees: Local Approach",
abstract = "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.",
keywords = "Decision rules systems, Decision trees, Space complexity, Time complexity, Time-space tradeoff",
author = "Kerven Durdymyradov and Mikhail Moshkov",
note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE International Conference on Big Data, BigData 2023 ; Conference date: 15-12-2023 Through 18-12-2023",
year = "2023",
doi = "10.1109/BigData59044.2023.10386989",
language = "English (US)",
series = "Proceedings - 2023 IEEE International Conference on Big Data, BigData 2023",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "6040--6045",
editor = "Jingrui He and Themis Palpanas and Xiaohua Hu and Alfredo Cuzzocrea and Dejing Dou and Dominik Slezak and Wei Wang and Aleksandra Gruca and Lin, \{Jerry Chun-Wei\} and Rakesh Agrawal",
booktitle = "Proceedings - 2023 IEEE International Conference on Big Data, BigData 2023",
address = "United States",
}