{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T04:50:07Z","timestamp":1778907007475,"version":"3.51.4"},"reference-count":23,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T00:00:00Z","timestamp":1696291200000},"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 conventional decision tables closed relative to the removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study the dependence of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We also study the dependence of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that a nondeterministic decision tree can be interpreted as a set of true decision rules that covers all rows of the table.<\/jats:p>","DOI":"10.3390\/e25101411","type":"journal-article","created":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T01:48:17Z","timestamp":1696297697000},"page":"1411","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes"],"prefix":"10.3390","volume":"25","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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,3]]},"reference":[{"key":"ref_1","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J. (1984). Classification and Regression Trees, Wadsworth and Brooks."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chikalov, I., Lozin, V.V., Lozina, I., Moshkov, M., Nguyen, H.S., Skowron, A., and Zielosko, B. (2013). Three Approaches to Data Analysis\u2014Test Theory, Rough Sets and Logical Analysis of Data, Springer. Intelligent Systems Reference Library.","DOI":"10.1007\/978-3-642-28667-4"},{"key":"ref_3","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_4","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_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\/6604"},{"key":"ref_7","first-page":"244","article-title":"Time Complexity of Decision Trees","volume":"3","author":"Moshkov","year":"2005","journal-title":"Trans. Rough Sets"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Moshkov, M., and Zielosko, B. (2011). Combinatorial Machine Learning\u2014A Rough Set Approach, Springer. Studies in Computational Intelligence.","DOI":"10.1007\/978-3-642-20995-6"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Moshkov, M. (2020). Comparative Analysis of Deterministic and Nondeterministic Decision Trees, Springer. Intelligent Systems Reference Library.","DOI":"10.1007\/978-3-030-41728-4"},{"key":"ref_10","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_11","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_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.]."},{"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","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_16","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, Cornell University, Ithaca, NY, USA.","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"ref_17","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_18","unstructured":"Markov, A.A. (1989). Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis, Gorky University Press. (In Russian)."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ostonov, A., and Moshkov, M. (2023). Comparative analysis of deterministic and nondeterministic decision trees for decision tables from closed classes. arXiv.","DOI":"10.2139\/ssrn.4510959"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ostonov, A., and Moshkov, M. (2023). Deterministic and strongly nondeterministic decision trees for decision tables from closed classes. arXiv.","DOI":"10.2139\/ssrn.4510959"},{"key":"ref_21","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_22","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_23","first-page":"131","article-title":"Conditional tests","volume":"Volume 40","author":"Yablonskii","year":"1983","journal-title":"Problemy Kibernetiki"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/10\/1411\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:04:23Z","timestamp":1760130263000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/10\/1411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,3]]},"references-count":23,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["e25101411"],"URL":"https:\/\/doi.org\/10.3390\/e25101411","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,3]]}}}