{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T08:28:40Z","timestamp":1766305720797,"version":"3.48.0"},"reference-count":25,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T00:00:00Z","timestamp":1759622400000},"content-version":"vor","delay-in-days":277,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Procedia Computer Science"],"published-print":{"date-parts":[[2025]]},"DOI":"10.1016\/j.procs.2025.10.093","type":"journal-article","created":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T22:13:48Z","timestamp":1762467228000},"page":"6233-6242","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Comparison of Complexity of Regular and Oblivious Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes"],"prefix":"10.1016","volume":"270","author":[{"given":"Azimkhon","family":"Ostonov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Moshkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"2019","series-title":"Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining. volume 146 of Intelligent Systems Reference Library","author":"AbouEisha","key":"10.1016\/j.procs.2025.10.093_bib1"},{"key":"10.1016\/j.procs.2025.10.093_bib2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(03)00186-0","article-title":"Variants of the majority problem","volume":"137","author":"Aigner","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"10.1016\/j.procs.2025.10.093_bib3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.3233\/FI-2019-1785","article-title":"A classifier based on a decision tree with temporal cuts","volume":"165","author":"Bazan","year":"2019","journal-title":"Fundam. Informaticae"},{"key":"10.1016\/j.procs.2025.10.093_bib4","series-title":"Generic oracles and oracle classes (extended abstract), in: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987","first-page":"118","author":"Blum","year":"1987"},{"year":"1984","series-title":"Classification and Regression Trees","author":"Breiman","key":"10.1016\/j.procs.2025.10.093_bib5"},{"key":"10.1016\/j.procs.2025.10.093_bib6","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."},{"year":"2013","series-title":"Three Approaches to Data Analysis - Test Theory, Rough Sets and Logical Analysis of Data. volume 41 of Intelligent Systems Reference Library","author":"Chikalov","key":"10.1016\/j.procs.2025.10.093_bib7"},{"year":"2024","series-title":"Decision Trees Versus Systems of Decision Rules: A Rough Set Approach. volume 160 of Studies in Big Data","author":"Durdymyradov","key":"10.1016\/j.procs.2025.10.093_bib8"},{"key":"10.1016\/j.procs.2025.10.093_bib9","doi-asserted-by":"crossref","unstructured":"F\u00fcrnkranz, J., Gamberger, D., Lavrac, N., 2012. Foundations of Rule Learning. Cognitive Technologies, Springer.","DOI":"10.1007\/978-3-540-75197-7"},{"key":"10.1016\/j.procs.2025.10.093_bib10","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Hemachandra, L.A., 1987. One-way functions, robustness, and the non-isomorphism of NP-complete sets, in: Proceedings of the Second Annual Conference on Structure in Complexity Theory, Cornell University, Ithaca, New York, USA, June 16-19, 1987, IEEE Computer Society.","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"10.1016\/j.procs.2025.10.093_bib11","series-title":"Oblivious decision trees, graphs, and top-down pruning, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montr\u00e9al Qu\u00e9bec, Canada, August 20-25 1995, 2 Volumes","first-page":"1071","author":"Kohavi","year":"1995"},{"key":"10.1016\/j.procs.2025.10.093_bib12","unstructured":"Mironov, A., Khuziev, I., 2022. Optimization of oblivious decision tree ensembles evaluation for CPU. CoRR abs\/2211.00391. URL: https:\/\/doi.org\/10.48550\/arXiv.2211.00391, doi: 10.48550\/ARXIV.2211.00391, arXiv:2211.00391."},{"key":"10.1016\/j.procs.2025.10.093_bib13","doi-asserted-by":"crossref","unstructured":"Moshkov, M., 2005. Time complexity of decision trees, in: Peters, J.F., Skowron, A. (Eds.), Trans. Rough Sets III. Springer. volume 3400 of Lecture Notes in Computer Science, pp. 244\u2013459.","DOI":"10.1007\/11427834_12"},{"key":"10.1016\/j.procs.2025.10.093_bib14","doi-asserted-by":"crossref","first-page":"2837","DOI":"10.1016\/j.disc.2007.03.002","article-title":"On the class of restricted linear information systems","volume":"307","author":"Moshkov","year":"2007","journal-title":"Discret. Math."},{"year":"2011","series-title":"Combinatorial Machine Learning - A Rough Set Approach. volume 360 of Studies in Computational Intelligence","author":"Moshkov","key":"10.1016\/j.procs.2025.10.093_bib15"},{"key":"10.1016\/j.procs.2025.10.093_bib16","series-title":"On efficient construction of decision trees from large databases, in: Ziarko, W., Yao, Y.Y. (Eds.), Rough Sets and Current Trends in Computing, Second International Conference, RSCTC 2000 Banff, Canada, October 16-19, 2000, Revised Papers","first-page":"354","author":"Nguyen","year":"2000"},{"year":"2025","series-title":"Comparison of complexity of regular and oblivious decision trees for decision tables from closed classes, in: Proceedings of the International Joint Conference on Rough Sets","author":"Ostonov","key":"10.1016\/j.procs.2025.10.093_bib17"},{"key":"10.1016\/j.procs.2025.10.093_bib18","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":"10.1016\/j.procs.2025.10.093_bib19","unstructured":"Popov, S., Morozov, S., Babenko, A., 2019. Neural oblivious decision ensembles for deep learning on tabular data. CoRR abs\/1909.06312. URL: http:\/\/arxiv.org\/abs\/1909.06312."},{"key":"10.1016\/j.procs.2025.10.093_bib20","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1109\/TSMCC.2004.843247","article-title":"Top-down induction of decision trees classifiers - a survey","volume":"35","author":"Rokach","year":"2005","journal-title":"IEEE Trans. Syst. Man Cybern. Part C"},{"year":"2007","series-title":"Data Mining with Decision Trees - Theory and Applications. volume 69 of Series in Machine Perception and Artificial Intelligence","author":"Rokach","key":"10.1016\/j.procs.2025.10.093_bib21"},{"key":"10.1016\/j.procs.2025.10.093_bib22","doi-asserted-by":"crossref","unstructured":"Skowron, A., Jankowski, A., Swiniarski, R.W., 2015. Foundations of rough sets, in: Kacprzyk, J., Pedrycz, W. (Eds.), Springer Handbook of Computational Intelligence. Springer. Springer Handbooks, pp. 331\u2013348.","DOI":"10.1007\/978-3-662-43505-2_21"},{"key":"10.1016\/j.procs.2025.10.093_bib23","doi-asserted-by":"crossref","unstructured":"Skowron, A., Rauszer, C., 1992. The discernibility matrices and functions in information systems, in: Slowinski, R. (Ed.), Intelligent Decision Support - Handbook of Applications and Advances of the Rough Sets Theory. Springer. volume 11 of Theory and Decision Library, pp. 331\u2013362.","DOI":"10.1007\/978-94-015-7975-9_21"},{"first-page":"376","year":"2020","author":"Slezak","key":"10.1016\/j.procs.2025.10.093_bib24"},{"key":"10.1016\/j.procs.2025.10.093_bib25","first-page":"385","article-title":"Query complexity, or why is it difficult to separate NPA \u2229 coNPA from PA by random oracles A?","volume":"9","author":"Tardos","year":"1989","journal-title":"Comb."}],"container-title":["Procedia Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S187705092503426X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S187705092503426X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T08:24:40Z","timestamp":1766305480000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S187705092503426X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":25,"alternative-id":["S187705092503426X"],"URL":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.093","relation":{},"ISSN":["1877-0509"],"issn-type":[{"type":"print","value":"1877-0509"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Comparison of Complexity of Regular and Oblivious Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes","name":"articletitle","label":"Article Title"},{"value":"Procedia Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.093","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}