{"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":1778907007438,"version":"3.51.4"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031656644","type":"print"},{"value":"9783031656651","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-65665-1_11","type":"book-chapter","created":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T07:04:54Z","timestamp":1721804694000},"page":"173-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Complexity of\u00a0Deterministic and\u00a0Nondeterministic Decision Trees for\u00a0Decision Tables with\u00a0Many-Valued Decisions from\u00a0Closed Classes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5763-9751","authenticated-orcid":false,"given":"Azimkhon","family":"Ostonov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0085-9483","authenticated-orcid":false,"given":"Mikhail","family":"Moshkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,25]]},"reference":[{"key":"11_CR1","series-title":"Intelligent Systems Reference Library","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-12854-8","volume-title":"Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions","author":"F Alsolami","year":"2020","unstructured":"Alsolami, F., Azad, M., Chikalov, I., Moshkov, M.: Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions. ISRL, vol. 156. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-12854-8"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Blum, M., Impagliazzo, R.: Generic oracles and oracle classes (extended abstract). In: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27\u201329 October 1987, pp. 118\u2013126. IEEE Computer Society (1987)","DOI":"10.1109\/SFCS.1987.30"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1109\/69.842268","volume":"12","author":"E Boros","year":"2000","unstructured":"Boros, E., Hammer, P.L., Ibaraki, T., Kogan, A., Mayoraz, E., Muchnik, I.B.: An implementation of logical analysis of data. IEEE Trans. Knowl. Data Eng. 12(2), 292\u2013306 (2000)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"9","key":"11_CR4","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1016\/j.patcog.2004.03.009","volume":"37","author":"MR Boutell","year":"2004","unstructured":"Boutell, M.R., Luo, J., Shen, X., Brown, C.M.: Learning multi-label scene classification. Pattern Recogn. 37(9), 1757\u20131771 (2004)","journal-title":"Pattern Recogn."},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75197-7","volume-title":"Foundations of Rule Learning. Cognitive Technologies","author":"J F\u00fcrnkranz","year":"2012","unstructured":"F\u00fcrnkranz, J., Gamberger, D., Lavrac, N.: Foundations of Rule Learning. Cognitive Technologies. Springer, Cham (2012). https:\/\/doi.org\/10.1007\/978-3-540-75197-7"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Hemachandra, L.A.: 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, 16\u201319 June 1987. IEEE Computer Society (1987)","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"11_CR8","unstructured":"Molnar, C.: Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, 2nd edn. (2022). https:\/\/christophm.github.io\/interpretable-ml-book\/"},{"key":"11_CR9","unstructured":"Moshkov, M.: On depth of conditional tests for tables from closed classes. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis, pp. 78\u201386. Gorky University Press, Gorky (1989). (in Russian)"},{"key":"11_CR10","series-title":"Intelligent Systems Reference Library","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-41728-4","volume-title":"Comparative Analysis of Deterministic and Nondeterministic Decision Trees","author":"M Moshkov","year":"2020","unstructured":"Moshkov, M.: Comparative Analysis of Deterministic and Nondeterministic Decision Trees. ISRL, vol. 179. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-41728-4"},{"key":"11_CR11","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69029-0","volume-title":"Partial Covers, Reducts and Decision Rules in Rough Sets - Theory and Applications","author":"M Moshkov","year":"2008","unstructured":"Moshkov, M., Piliszczuk, M., Zielosko, B.: Partial Covers, Reducts and Decision Rules in Rough Sets - Theory and Applications. Studies in Computational Intelligence, vol. 145. Springer, Cham (2008). https:\/\/doi.org\/10.1007\/978-3-540-69029-0"},{"key":"11_CR12","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20995-6","volume-title":"Combinatorial Machine Learning - A Rough Set Approach","author":"M Moshkov","year":"2011","unstructured":"Moshkov, M., Zielosko, B.: Combinatorial Machine Learning - A Rough Set Approach. Studies in Computational Intelligence, vol. 360. Springer, Cham (2011). https:\/\/doi.org\/10.1007\/978-3-642-20995-6"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Ostonov, A., Moshkov, M.: Comparative analysis of deterministic and nondeterministic decision trees for decision tables from closed classes. arXiv:2304.10594 [cs.CC] (2023)","DOI":"10.2139\/ssrn.4604939"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-031-50959-9_7","volume-title":"Rough Sets","author":"A Ostonov","year":"2023","unstructured":"Ostonov, A., Moshkov, M.: Deterministic and nondeterministic decision trees for decision tables with many-valued decisions from closed classes. In: Campagner, A., Urs Lenz, O., Xia, S., Slezak, D., Was, J., Yao, J. (eds.) IJCRS 2023. Lecture Notes in Computer Science, vol. 14481, pp. 89\u2013104. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-50959-9_7"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Ostonov, A., Moshkov, M.: Deterministic and strongly nondeterministic decision trees for decision tables from closed classes. arXiv:2305.06093 [cs.CC] (2023)","DOI":"10.2139\/ssrn.4604939"},{"issue":"10","key":"11_CR16","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.3390\/e25101411","volume":"25","author":"A Ostonov","year":"2023","unstructured":"Ostonov, A., Moshkov, M.: On complexity of deterministic and nondeterministic decision trees for conventional decision tables from closed classes. Entropy 25(10), 1411 (2023)","journal-title":"Entropy"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Ostonov, A., Moshkov, M.: Greedy algorithm for construction of deterministic decision trees for conventional decision tables from closed classes. In: Proceedings of the International Joint Conference on Rough Sets (2024, to appear)","DOI":"10.2139\/ssrn.4604939"},{"issue":"3","key":"11_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0306-4379(81)90023-5","volume":"6","author":"Z Pawlak","year":"1981","unstructured":"Pawlak, Z.: Information systems theoretical foundations. Inf. Syst. 6(3), 205\u2013218 (1981)","journal-title":"Inf. Syst."},{"issue":"1","key":"11_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ins.2006.06.003","volume":"177","author":"Z Pawlak","year":"2007","unstructured":"Pawlak, Z., Skowron, A.: Rudiments of rough sets. Inf. Sci. 177(1), 3\u201327 (2007)","journal-title":"Inf. Sci."},{"key":"11_CR20","series-title":"Annals of Mathematics Studies","volume-title":"Two-Valued Iterative Systems of Mathematical Logic","author":"E Post","year":"1941","unstructured":"Post, E.: Two-Valued Iterative Systems of Mathematical Logic. Annals of Mathematics Studies, vol. 5. Princeton University Press, London (1941)"},{"key":"11_CR21","volume-title":"C4.5: Programs for Machine Learning","author":"JR Quinlan","year":"1993","unstructured":"Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, Burlington (1993)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory, Ser. B 92(2), 325\u2013357 (2004)","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Rokach, L., Maimon, O.: Data Mining with Decision Trees - Theory and Applications. Series in Machine Perception and Artificial Intelligence, vol.\u00a069. World Scientific (2007)","DOI":"10.1142\/9789812771728"},{"key":"11_CR24","series-title":"TDLD","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-94-015-7975-9_21","volume-title":"Intelligent Decision Support","author":"A Skowron","year":"1992","unstructured":"Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: Slowinski, R. (ed.) Intelligent Decision Support. TDLD, vol. 11, pp. 331\u2013362. Springer, Cham (1992). https:\/\/doi.org\/10.1007\/978-94-015-7975-9_21"},{"issue":"4","key":"11_CR25","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G Tardos","year":"1989","unstructured":"Tardos, G.: Query complexity, or why is it difficult to separate $${NP}^{A}\\cap co{NP}^{A}$$ from $${P}^{A}$$ by random oracles $${A}$$? Combinatorica 9(4), 385\u2013392 (1989)","journal-title":"Combinatorica"},{"issue":"2","key":"11_CR26","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10994-008-5077-3","volume":"73","author":"C Vens","year":"2008","unstructured":"Vens, C., Struyf, J., Schietgat, L., Dzeroski, S., Blockeel, H.: Decision trees for hierarchical multi-label classification. Mach. Learn. 73(2), 185\u2013214 (2008)","journal-title":"Mach. Learn."},{"issue":"1","key":"11_CR27","doi-asserted-by":"publisher","first-page":"2291","DOI":"10.1016\/j.artint.2011.10.002","volume":"176","author":"Z Zhou","year":"2012","unstructured":"Zhou, Z., Zhang, M., Huang, S., Li, Y.: Multi-instance multi-label learning. Artif. Intell. 176(1), 2291\u20132320 (2012)","journal-title":"Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Rough Sets"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-65665-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T07:07:42Z","timestamp":1721804862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-65665-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031656644","9783031656651"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-65665-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"25 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJCRS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Joint Conference on Rough Sets","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Halifax, NS","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ijcrs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ijcrs24.cs.smu.ca","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}