A binary complete decision table with many-valued decisions is a table with
attributes and
pairwise distinct rows filled with numbers from the set
. Each row of this table is labeled with a nonempty finite set of decisions. For a given row of the table, the task is to find a decision from the set of decisions attached to the row. Such tables are generalizations of Boolean functions. They can also be viewed as representations of various problems related to systems of decision rules. In this paper, we consider three types of classes of binary complete decision tables with many-valued decisions, closed with respect to removal of columns and changing of decisions. For tables from these classes, we study the relationships between the minimum weighted depth of deterministic, nondeterministic, and (for one type of classes) strongly nondeterministic decision trees and the total weight of attributes attached to columns. Note that nondeterministic decision trees and strongly nondeterministic decision trees for decision tables can be interpreted as a way of representing the two types of systems of decision rules for these tables.
References
[1]
Durdymyradov, K., Moshkov, M. and Ostonov, A. (2025) Decision Trees Versus Systems of Decision Rules—A Rough Set Approach. Springer. https://doi.org/10.1007/978-3-031-71586-0
[2]
Breiman, L., Friedman, J.H. and Olshen, R.A. (1984) Classification and Regression Trees. Chapman and Hall/CRC. https://doi.org/10.1201/9781315139470
[3]
Moshkov, M.J. (2005) Time Complexity of Decision Trees. In: Peters, J.F. and Skowron, A., Eds., Lecture Notes in Computer Science, Springer, 244-459. https://doi.org/10.1007/11427834_12
[4]
Moshkov, M. (2020) Comparative Analysis of Deterministic and Nondeterministic Decision Trees. Springer. https://doi.org/10.1007/978-3-030-41728-4
[5]
Quinlan, J.R. (1993) C4.5: Programs for Machine Learning. Morgan Kaufmann. https://doi.org/10.1007/BF00993309
[6]
Rokach, L. and Maimon, O. (2007) Data Mining with Decision Trees—Theory and Applications. World Scientific Publishing Co. Pte. Ltd. https://doi.org/10.1142/9789812771728
[7]
Boros, E., Hammer, P.L., Ibaraki, T., Kogan, A., Mayoraz, E. and Muchnik, I. (2000) An Implementation of Logical Analysis of Data. IEEE Transactions on Knowledge and Data Engineering, 12, 292-306. https://doi.org/10.1109/69.842268
[8]
Chikalov, I., Lozin, V.V., Lozina, I., Moshkov, M., Nguyen, H.S., Skowron, A. and Zielosko, B. (2013) Three Approaches to Data Analysis—Test Theory, Rough Sets and Logical Analysis of Data. Springer. https://doi.org/10.1007/978-3-642-28667-4
[9]
Fürnkranz, J., Gamberger, D. and Lavrac, N. (2012) Foundations of Rule Learning. Springer. https://doi.org/10.1007/978-3-540-75197-7
[10]
Moshkov, M. and Zielosko, B. (2011) Combinatorial Machine Learning—A Rough Set Approach. Springer. https://doi.org/10.1007/978-3-642-20995-6
[11]
Pawlak, Z. and Skowron, A. (2007) Rudiments of Rough Sets. Information Sciences, 177, 3-27. https://doi.org/10.1016/j.ins.2006.06.003
[12]
Molnar, C. (2022) Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, Self-Published https://christophm.github.io/interpretable-ml-book/
[13]
Boutell, M.R., Luo, J., Shen, X. and Brown, C.M. (2004) Learning Multi-Label Scene Classification. Pattern Recognition, 37, 1757-1771. https://doi.org/10.1016/j.patcog.2004.03.009
[14]
Vens, C., Struyf, J., Schietgat, L., Džeroski, S. and Blockeel, H. (2008) Decision Trees for Hierarchical Multi-Label Classification. Machine Learning, 73, 185-214. https://doi.org/10.1007/s10994-008-5077-3
[15]
Zhou, Z., Zhang, M., Huang, S. and Li, Y. (2012) Multi-Instance Multi-Label Learning. Artificial Intelligence, 176, 2291-2320. https://doi.org/10.1016/j.artint.2011.10.002
[16]
Alsolami, F., Azad, M., Chikalov, I. and Moshkov, M. (2020) Decision and Inhibitory Trees and Rules for Decision Tables with Many-Valued Decisions. Springer. https://doi.org/10.1007/978-3-030-12854-8
[17]
Post, E. (1941) Two-Valued Iterative Systems of Mathematical Logic. Vol. 5, Princeton University Press. https://doi.org/10.2307/2268608
[18]
Robertson, N. and Seymour, P.D. (2004) Graph Minors. XX. Wagner’s Conjecture. Journal of Combinatorial Theory, Series B, 92, 325-357. https://doi.org/10.1016/j.jctb.2004.08.001
[19]
Pawlak, Z. (1981) Information Systems Theoretical Foundations. Information Systems, 6, 205-218. https://doi.org/10.1016/0306-4379(81)90023-5
[20]
Blum, M. and Impagliazzo, R. (1987) Generic Oracles and Oracle Classes. 28th Annual Symposium on Foundations of Computer Science (SFCS 1987), Los Angeles, 27-29 October 1987, 118-126. https://doi.org/10.1109/sfcs.1987.30
[21]
Hartmanis, J. and Hemachandra, L.A. (1987) One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets. Proceeding Structure in Complexity Theory, Ithaca, 16-19 June 1987, 160-174. https://doi.org/10.1109/psct.1987.10319267
[22]
Tardos, G. (1989) Query Complexity, or Why Is It Difficult to Separate NPA ∩ coNPA from PA by Random Oracles A? Combinatorica, 9, 385-392. https://doi.org/10.1007/bf02125350
[23]
Buhrman, H. and de Wolf, R. (2002) Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288, 21-43. https://doi.org/10.1016/s0304-3975(01)00144-x
[24]
Ostonov A. and Moshkov M. (2025) Binary Complete Decision Tables with Many-valued Decisions from Closed Classes. 20th International Conference on Intelligent Systems and Knowledge Engineering (ISKE 2025), Shunde, 21-23 November 2025.
[25]
Durdymyradov, K. and Moshkov, M. (2025) Weighted Depth of Deterministic and Non-Deterministic Decision Trees for Recognition Properties of Decision Rule Systems. 29th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems (KES 2025), Osaka, 10-12 September 2025.
