{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T03:01:57Z","timestamp":1770692517179,"version":"3.49.0"},"reference-count":23,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"King Abdullah University of Science and Technology"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we consider classes of decision tables with many-valued decisions closed under operations of the removal of columns, the changing of decisions, the permutation of columns, and the duplication of columns. We study relationships among three parameters of these tables: the complexity of a decision table (if we consider the depth of the decision trees, then the complexity of a decision table is the number of columns in it), the minimum complexity of a deterministic decision tree, and the minimum complexity of a nondeterministic decision tree. We consider the rough classification of functions characterizing relationships and enumerate all possible seven types of relationships.<\/jats:p>","DOI":"10.3390\/e26060519","type":"journal-article","created":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T08:48:31Z","timestamp":1718614111000},"page":"519","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Comparative Analysis of Deterministic and Nondeterministic Decision Trees for Decision Tables from Closed Classes"],"prefix":"10.3390","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5763-9751","authenticated-orcid":false,"given":"Azimkhon","family":"Ostonov","sequence":"first","affiliation":[{"name":"Computer, Electrical and Mathematical Sciences & Engineering Division and Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0085-9483","authenticated-orcid":false,"given":"Mikhail","family":"Moshkov","sequence":"additional","affiliation":[{"name":"Computer, Electrical and Mathematical Sciences & Engineering Division and Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1016\/j.patcog.2004.03.009","article-title":"Learning multi-label scene classification","volume":"37","author":"Boutell","year":"2004","journal-title":"Pattern Recognit."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10994-008-5077-3","article-title":"Decision trees for hierarchical multi-label classification","volume":"73","author":"Vens","year":"2008","journal-title":"Mach. Learn."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2291","DOI":"10.1016\/j.artint.2011.10.002","article-title":"Multi-instance multi-label learning","volume":"176","author":"Zhou","year":"2012","journal-title":"Artif. Intell."},{"key":"ref_4","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J. (1984). Classification and Regression Trees, Wadsworth and Brooks."},{"key":"ref_5","unstructured":"Quinlan, J.R. (1993). C4.5: Programs for Machine Learning, Morgan Kaufmann."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Rokach, L., and Maimon, O. (2007). Data Mining with Decision Trees\u2014Theory and Applications, World Scientific.","DOI":"10.1142\/9789812771728"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Ostonov, A., and Moshkov, M. (2023). On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes. Entropy, 25.","DOI":"10.2139\/ssrn.4604939"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02614316","article-title":"Logical analysis of numerical data","volume":"79","author":"Boros","year":"1997","journal-title":"Math. Program."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/69.842268","article-title":"An Implementation of Logical Analysis of Data","volume":"12","author":"Boros","year":"2000","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"F\u00fcrnkranz, J., Gamberger, D., and Lavrac, N. (2012). Foundations of Rule Learning, Springer. Cognitive Technologies.","DOI":"10.1007\/978-3-540-75197-7"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Pawlak, Z. (1991). Rough Sets\u2014Theoretical Aspects of Reasoning about Data, Kluwer.","DOI":"10.1007\/978-94-011-3534-4"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.ins.2006.06.003","article-title":"Rudiments of rough sets","volume":"177","author":"Pawlak","year":"2007","journal-title":"Inf. Sci."},{"key":"ref_13","unstructured":"Molnar, C. (2022). Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, Independent Publishers. [2nd ed.]. Available online: https:\/\/christophm.github.io\/interpretable-ml-book\/."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Blum, M., and Impagliazzo, R. (1987, January 27\u201329). Generic Oracles and Oracle Classes (Extended Abstract). Proceedings of the 28th Annual Symposium on Foundations of Computer Science, Los Angeles, CA, USA.","DOI":"10.1109\/SFCS.1987.30"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., and Hemachandra, L.A. (1987, January 16\u201319). One-way functions, robustness, and the non-isomorphism of NP-complete sets. Proceedings of the Second Annual Conference on Structure in Complexity Theory, Ithaca, NY, USA.","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02125350","article-title":"Query complexity, or why is it difficult to separate NPA\u2229coNPA from PA by random oracles A?","volume":"9","author":"Tardos","year":"1989","journal-title":"Combinatorica"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","article-title":"Complexity measures and decision tree complexity: A survey","volume":"288","author":"Buhrman","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0306-4379(81)90023-5","article-title":"Information systems theoretical foundations","volume":"6","author":"Pawlak","year":"1981","journal-title":"Inf. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Post, E. (1941). Two-Valued Iterative Systems of Mathematical Logic, Princeton University Press. Annals of Mathematics Studies.","DOI":"10.1515\/9781400882366"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","article-title":"Graph Minors. XX. Wagner\u2019s conjecture","volume":"92","author":"Robertson","year":"2004","journal-title":"J. Comb. Theory, Ser. B"},{"key":"ref_21","unstructured":"Markov, A.A. (1989). On depth of conditional tests for tables from closed classes. Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis, Gorky University Press. (In Russian)."},{"key":"ref_22","first-page":"125","article-title":"Comparative Analysis of Deterministic and Nondeterministic Decision Tree Complexity. Local Approach","volume":"4","author":"Moshkov","year":"2005","journal-title":"Trans. Rough Sets"},{"key":"ref_23","first-page":"244","article-title":"Time Complexity of Decision Trees","volume":"3","author":"Moshkov","year":"2005","journal-title":"Trans. Rough Sets"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/6\/519\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:59:49Z","timestamp":1760108389000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/6\/519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":23,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["e26060519"],"URL":"https:\/\/doi.org\/10.3390\/e26060519","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,17]]}}}