{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:03:00Z","timestamp":1778677380001,"version":"3.51.4"},"reference-count":21,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, based on the results of rough set theory, test theory, and exact learning, we investigate decision trees over infinite sets of binary attributes represented as infinite binary information systems. We define the notion of a problem over an information system and study three functions of the Shannon type, which characterize the dependence in the worst case of the minimum depth of a decision tree solving a problem on the number of attributes in the problem description. The considered three functions correspond to (i) decision trees using attributes, (ii) decision trees using hypotheses (an analog of equivalence queries from exact learning), and (iii) decision trees using both attributes and hypotheses. The first function has two possible types of behavior: logarithmic and linear (this result follows from more general results published by the author earlier). The second and the third functions have three possible types of behavior: constant, logarithmic, and linear (these results were published by the author earlier without proofs that are given in the present paper). Based on the obtained results, we divided the set of all infinite binary information systems into four complexity classes. In each class, the type of behavior for each of the considered three functions does not change.<\/jats:p>","DOI":"10.3390\/e24010116","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T09:10:36Z","timestamp":1641978636000},"page":"116","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Depth of Decision Trees with Hypotheses"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0085-9483","authenticated-orcid":false,"given":"Mikhail","family":"Moshkov","sequence":"first","affiliation":[{"name":"Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00116828","article-title":"Queries and concept learning","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learn."},{"key":"ref_2","first-page":"341","article-title":"Rough sets","volume":"11","author":"Pawlak","year":"1982","journal-title":"Int. J. Parallel Program."},{"key":"ref_3","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_4","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_5","first-page":"270","article-title":"Logical methods of control of work of electric schemes","volume":"51","author":"Chegis","year":"1958","journal-title":"Trudy Mat. Inst. Steklov"},{"key":"ref_6","first-page":"123","article-title":"Minimizing depth of decision trees with hypotheses","volume":"Volume 12872","author":"Ramanna","year":"2021","journal-title":"Rough Sets\u2013International Joint Conference, Proceedings of the IJCRS 2021, Bratislava, Slovakia, 19\u201324 September 2021"},{"key":"ref_7","first-page":"232","article-title":"Minimizing number of nodes in decision trees with hypotheses","volume":"Volume 192","author":"Watrobski","year":"2021","journal-title":"Proceedings of the 25th International Conference on Knowledge\u2014Based and Intelligent Information & Engineering Systems (KES 2021)"},{"key":"ref_8","first-page":"126","article-title":"Sorting by decision trees with hypotheses (extended abstract)","volume":"Volume 2951","author":"Schlingloff","year":"2021","journal-title":"Proceedings of the 29th International Workshop on Concurrency, Specification and Programming, CS&P 2021"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Azad, M., Chikalov, I., Hussain, S., and Moshkov, M. (2021). Optimization of decision trees with hypotheses for knowledge representation. Electronics, 10.","DOI":"10.3390\/electronics10131580"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Azad, M., Chikalov, I., Hussain, S., and Moshkov, M. (2021). Entropy-based greedy algorithm for decision trees using hypotheses. Entropy, 23.","DOI":"10.3390\/e23070808"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.tcs.2003.11.004","article-title":"Queries revisited","volume":"313","author":"Angluin","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF00116827","article-title":"Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm","volume":"2","author":"Littlestone","year":"1988","journal-title":"Mach. Learn."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF00992674","article-title":"Lower bound methods and separation results for on-line learning models","volume":"9","author":"Maass","year":"1992","journal-title":"Mach. Learn."},{"key":"ref_14","first-page":"131","article-title":"Conditional tests","volume":"Volume 40","author":"Yablonskii","year":"1983","journal-title":"Problemy Kibernetiki"},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/11427834_12","article-title":"Time complexity of decision trees","volume":"Volume 3400","author":"Peters","year":"2005","journal-title":"Transactions on Rough Sets III"},{"key":"ref_17","unstructured":"Moshkov, M. (June, January 31). Test theory and problems of machine learning. Proceedings of the International School-Seminar on Discrete Mathematics and Mathematical Cybernetics, Ratmino, Russia."},{"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","first-page":"203","DOI":"10.1016\/0012-365X(94)00318-D","article-title":"Independence number and the complexity of families of sets","volume":"154","author":"Naiman","year":"1996","journal-title":"Discr. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","article-title":"On the density of families of sets","volume":"13","author":"Sauer","year":"1972","journal-title":"J. Comb. Theory A"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"241","DOI":"10.2140\/pjm.1972.41.247","article-title":"A combinatorial problem; stability and order for models and theories in infinitary languages","volume":"41","author":"Shelah","year":"1972","journal-title":"Pac. J. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/116\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:28:41Z","timestamp":1760365721000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010116"],"URL":"https:\/\/doi.org\/10.3390\/e24010116","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]}}}