Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Time Complexity of Decision Trees

  • Conference paper
Transactions on Rough Sets III

Part of the book series: Lecture Notes in Computer Science ((TRS,volume 3400))

  • 1421 Accesses

Abstract

The research monograph is devoted to the study of bounds on time complexity in the worst case of decision trees and algorithms for decision tree construction. The monograph is organized in four parts. In the first part (Sects. 1 and 2) results of the monograph are discussed in context of rough set theory and decision tree theory. In the second part (Sect. 3) some tools for decision tree investigation based on the notion of decision table are described. In the third part (Sects. 4–6) general results about time complexity of decision trees over arbitrary (finite and infinite) information systems are considered. The fourth part (Sects. 7–11) contains a collection of mathematical results on decision trees in areas of rough set theory and decision tree theory applications such as discrete optimization, analysis of acyclic programs, pattern recognition, fault diagnosis and probabilistic reasoning.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ahlswede, R., Wegener, I.: Suchprobleme. B.G. Teubner, Stuttgart (1979)

    Google Scholar 

  2. Alexeyev, V.E.: On entropy of two-dimensional fragmentary closed languages. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods and its Application, pp. 5–13. Gorky University Publishers, Gorky (1987) (in Russian)

    Google Scholar 

  3. Angluin, D.: Queries and concept learning. Machine Learning 2(4), 319–342 (1988)

    Google Scholar 

  4. Armstrong, D.B.: On finding of nearly minimal set of fault detection tests for combinatorial logic nets. IEEE Trans. on Elec. Comp. EC-15(1), 66–73 (1966)

    Article  MATH  Google Scholar 

  5. Bazan, J., Nguyen, H., Son, N.S., Hoa, S.P., Wróblewski, J.: Rough set algorithms in classification problems. In: Polkowski, L., Lin, T.Y., Tsumoto, S. (eds.) Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems (Studies in Fuzziness and Soft Computing 56), pp. 48–88. Phisica-Verlag/A Springer-Verlag Company (2000)

    Google Scholar 

  6. Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of 15th ACM Annual Symp. on Theory of Comput., pp. 80–86 (1983)

    Google Scholar 

  7. Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929–965 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  8. Bondarenko, V.A.: Non-polynomial lower bound on complexity of traveling salesman problem in one class of algorithms. Automation and Telemechanics 9, 45–50 (1983) (in Russian)

    MathSciNet  Google Scholar 

  9. Bondarenko, V.A.: Complexity bounds for combinatorial optimization problems in one class of algorithms. Russian Academy of Sciences Doklady 328(1), 22–24 (1993) (in Russian)

    MathSciNet  Google Scholar 

  10. Bondarenko, V.A., Yurov, S.V.: About a polyhedron of cubic graphs. Fundamenta Informaticae 25, 35–38 (1996)

    MATH  MathSciNet  Google Scholar 

  11. Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Chapman and Hall, New York (1984)

    MATH  Google Scholar 

  12. Brodley, C.E., Utgoff, P.E.: Multivariate decision trees. Machine Learning 19, 45–77 (1995)

    MATH  Google Scholar 

  13. Buntine, W.: Learning classification trees. Statistics and Computing 2, 63–73 (1992)

    Article  Google Scholar 

  14. Chegis, I.A., Yablonskii, S.V.: Logical methods of electric circuit control. Trudy MIAN SSSR 51, 270–360 (1958) (in Russian)

    MATH  Google Scholar 

  15. Chernikov, S.N.: Linear Inequalities. Nauka Publishers, Moscow (1968) (in Russian)

    Google Scholar 

  16. Chikalov, I.V.: On decision trees with minimal average depth. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 506–512. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  17. Chikalov, I.V.: Bounds on average weighted depth of decision trees depending only on entropy. In: Proceedings of the Seventh International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Paris, France, vol. 2, pp. 1190–1194 (1998)

    Google Scholar 

  18. Chikalov, I.V.: On average time complexity of decision trees and branching programs. Fundamenta Informaticae 39, 337–357 (1999)

    MATH  MathSciNet  Google Scholar 

  19. Chikalov, I.V.: Algorithm for constructing of decision trees with minimal average depth. In: Proceedings of the Eighth International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Madrid, Spain, vol. 1, pp. 376–379 (2000)

    Google Scholar 

  20. Chikalov, I.V.: Algorithm for constructing of decision trees with minimal number of nodes. In: Proceedings of the Second International Conference on Rough Sets and Current Trends in Computing, Banff, Canada, pp. 107–111 (2000)

    Google Scholar 

  21. Dietterich, T.G., Shavlik, J.W. (eds.): Readings in Machine Learning. Morgan Kaufmann, San Francisco (1990)

    Google Scholar 

  22. Dobkin, D., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput. 5(2), 181–186 (1976)

    Google Scholar 

  23. Dobkin, D., Lipton, R.J.: A lower bound of (1/2)n2 on linear search programs for the knapsack problem. J. Comput. Syst. Sci. 16, 413–417 (1978)

    Google Scholar 

  24. Dobkin, D., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comput. Syst. Sci. 18, 86–91 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  25. Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Recognition. Wiley, New York (2000)

    Google Scholar 

  26. Dudina, J.V., Knyazev, A.N.: On complexity of recognition of words from languages generated by context-free grammars with one nonterminal symbol. In: Bulletin of Nizhny Novgorod State University. Mathematical Simulation and Optimal Control 2, 214–223 (1998) (in Russian)

    Google Scholar 

  27. Eldred, B.D.: Test routines based on symbolic logic statements. J. ACM 6(1), 33–36 (1959)

    Article  MATH  MathSciNet  Google Scholar 

  28. Feige, U.: A threshold of ln n for approximating set cover (Preliminary version). In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing, pp. 314–318 (1996)

    Google Scholar 

  29. Garey, M.R., Jonson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.N. Freeman and Company, San Francisco (1979)

    Google Scholar 

  30. Goldman, R.S., Chipulis, V.P.: Diagnosis of iteration-free combinatorial circuits. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol. 14, pp. 3–15. Nauka Publishers, Novosibirsk (1969) (in Russian)

    Google Scholar 

  31. Grigoriev, D., Karpinski, M., Vorobjov, N.: Improved lower bound on testing membership to a polyhedron by algebraic decision trees. In: Proceedings IEEE FOCS, pp. 258–265 (1995)

    Google Scholar 

  32. Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, Berlin (2001)

    MATH  Google Scholar 

  33. Hegedüs, T.: Generalized teaching dimensions and the query complexity of learning. In: Proceedings of the 8th Annual ACM Conference on Computational Learning Theory, Santa Cruz, USA, pp. 108–117. ACM, New York (1995)

    Chapter  Google Scholar 

  34. Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V.V., Wilkins, D.: How many queries are needed to learn? J. ACM 43(5), 840–862 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  35. Humby, E.: Programs from Decision Tables. Macdonald, London, American Elsevier, New York (1973)

    Google Scholar 

  36. Imam, I.F., Michalski, R.S.: Learning decision trees from decision rules: a method and initial results from a comparative study. Journal of Intelligent Information Systems 2, 279–304 (1993)

    Article  Google Scholar 

  37. Inuiguchi, M., Tsumoto, S., Hirano, S. (eds.): Rough Set Theory and Granular Computing. Fuzziness and Soft Computing 125. Phisica-Verlag, A Springer-Verlag Company, Hidleberg (2003)

    Google Scholar 

  38. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9, 256–278 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  39. Jordan, M.I. (ed.): Learning in Graphical Models. MIT Press, Cambridge (1999)

    Google Scholar 

  40. Karavai, M.F.: Diagnosis of tree-like circuits in arbitrary basis. Automation and Telemechanics 1, 173–181 (1973) (in Russian)

    Google Scholar 

  41. Knyazev, A.N.: On recognition of words from languages generated by linear grammars with one nonterminal symbol. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 111–114. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  42. Knyazev, A.N.: On recognition of words from languages generated by 1-contextfree grammars. In: Proceedings of the Twelfth International Conference Problems of Theoretical Cybernetics, Part 1. Nizhny Novgorod, Russia, p. 96 (1999) (in Russian)

    Google Scholar 

  43. Knyazev, A.N.: On recognition of words from languages generated by contextfree grammars with one nonterminal symbol. In: Proceedings of the Eighth International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Madrid, Spain, vol. 1, pp. 1945–1948 (2000)

    Google Scholar 

  44. Komorowski, J., Pawlak, Z., Polkowski, L., Skowron, A.: Rough sets. A tutorial. In: Pal, S.K., Skowron, A. (eds.) Rough-Fuzzy Hybridization: A New Trend in Decision-Making, pp. 3–98. Springer, Singapore (1999)

    Google Scholar 

  45. Kospanov, E.S.: On algorithm for construction of simple enough tests. Discrete Analysis, vol. 8, pp. 43–47. Nauka Publishers, Novosibirsk (1966) (in Russian)

    Google Scholar 

  46. Kurosh, A.G.: Higher Algebra, 11th edn. Nauka Publishers, Moscow (1975) (in Russian)

    Google Scholar 

  47. Laskowski, M.C.: Vapnik-Chervonenkis classes of definable sets. J. London Math. Society 45, 377–384 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  48. Liu, H., Motoda, H.: Feature Selection for Knowledge Discovery and Data Mining. Kluwer Academic Publishers, Boston (1998)

    Book  MATH  Google Scholar 

  49. Liu, H., Motoda, H. (eds.): Feature Extraction, Construction and Selection: A Data Mining Approach. Kluwer Academic Publishers, Boston (1998)

    Google Scholar 

  50. Loh, W.-Y., Shih, Y.-S.: Split selection methods for classification trees. Statistica Sinica 7, 815–840 (1997)

    MATH  MathSciNet  Google Scholar 

  51. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  52. Madatyan, C.A.: Complete test for iteration-free contact circuits. In: Yablonskii, S.V. (ed.) Problems of Cybernetics, vol. 23, pp. 103–118. Nauka Publishers, Moscow (1970) (in Russian)

    Google Scholar 

  53. Markov, A.A.: Introduction into Coding Theory. Nauka Publishers, Moscow (1982)

    Google Scholar 

  54. Markov, A.A.: Circuit complexity of discrete optimization. Discrete Mathematics 4(3), 29–46 (1992) (in Russian)

    Google Scholar 

  55. Matiyasevich, J.V.: Diophantinity of enumerable sets. Academy of Sciences Doklady 191(2), 279–382 (1970)

    Google Scholar 

  56. Meyer auf der Heide, F.: A polynomial linear search algorithm for the ndimensional knapsack problem. J. ACM 31(3), 668–676 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  57. Meyer auf der Heide, F.: Fast algorithms for n-dimensional restrictions of hard problems. J. ACM 35(3), 740–747 (1988)

    Article  MathSciNet  Google Scholar 

  58. Michalski, R.S.: Discovering classification rules using variable-valued logic system VL1. In: Proceedings of the Third International Joint Conference on Artificial Intelligence, Stanford, USA, pp. 162–172 (1973)

    Google Scholar 

  59. Moore, E.F.: Gedanken-experiments on sequential machines. In: Shannon, C., McCarty, J. (eds.) Automata Studies, pp. 129–153. Princeton University Press, Princeton (1956)

    Google Scholar 

  60. Moravek, J.: On the complexity of discrete programming problems. Appl. Mat. 14(6), 442–474 (1969)

    MATH  MathSciNet  Google Scholar 

  61. Moravek, J.: A localization problems in geometry and complexity of discrete programming. Kybernetika 8(6), 498–516 (1972)

    MATH  MathSciNet  Google Scholar 

  62. Morzhakov, N.M.: On relationship between complexity of a set description and complexity of problem of linear form minimization on this set. In: Markov, A.A. (ed.) Combinatorial- Algebraic Methods in Applied Mathematics, pp. 83–98. Gorky University Publishers, Gorky (1985) (in Russian)

    Google Scholar 

  63. Morzhakov, N.M.: Bounds on complexity of construction of finite subsets of the set ℝn. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods in Applied Mathematics, pp. 84–106. Gorky University Publishers, Gorky (1986) (in Russian)

    Google Scholar 

  64. Morzhakov, N.M.: On possibilities of compression of finite subsets of the set ℝn. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods in Applied Mathematics, pp. 22–33. Gorky University Publishers, Gorky (1988) (in Russian)

    Google Scholar 

  65. Morzhakov, N.M.: On complexity of discrete extremal problem solving in the class of circuit algorithms. In: Yablonskii, S.V. (ed.) Mathematical Problems of Cybernetics, vol. 6, pp. 215–238. Nauka Publishers, Moscow (1996) (in Russian)

    Google Scholar 

  66. Moshkov, M.J.: Problems of consequence in some subalgebras of real function algebras. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods in Applied Mathematics, pp. 70–81. Gorky University Publishers, Gorky (1979) (in Russian)

    Google Scholar 

  67. Moshkov, M.J.: About uniqueness of uncancellable tests for recognition problems with linear decision rules. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods in Applied Mathematics, pp. 97–109. Gorky University Publishers, Gorky (1981) (in Russian)

    Google Scholar 

  68. Moshkov, M.J.: On conditional tests. Academy of Sciences Doklady 265(3), 550–552 (1982) (in Russian); English translation: Sov. Phys. Dokl. 27, 528–530 (1982)

    Google Scholar 

  69. Moshkov, M.J.: Test approach to extremal combinatorial problems. Ph.D. thesis. Gorky University (1982) (in Russian)

    Google Scholar 

  70. Moshkov, M.J.: Conditional tests. In: Yablonskii, S.V. (ed.) Problems of Cybernetics, vol. 40, pp. 131–170. Nauka Publishers, Moscow (1983) (in Russian)

    Google Scholar 

  71. Moshkov, M.J.: On problem of linear form minimization on finite set. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods in Applied Mathematics, pp. 98–119. Gorky University Publishers, Gorky (1985) (in Russian)

    Google Scholar 

  72. Moshkov, M.J.: Conditional tests for diagnosis of constant faults in combinatorial circuits. In: Proceedings of Eights All-Union Conference Problems of Theoretical Cybernetics, Part 2, Gorky, USSR, p. 50 (1988) (in Russian)

    Google Scholar 

  73. Moshkov, M.J.: On relationship of depth of deterministic and nondeterministic acyclic programs in the basis {x + y,x − y, 1; sign x}. In: Mathematical Problems in Computation Theory, Banach Center Publications, vol. 21, pp. 523–529. PWN, Polish Scientific Publishers, Warsaw (1988)

    Google Scholar 

  74. Moshkov, M.J.: 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–86. Gorky University Publishers, Gorky (1989) (in Russian)

    Google Scholar 

  75. Moshkov, M.J.: On minimization of object complexity. In: Proceedings of Workshop on Discrete Mathematics and its Applications, pp. 156–161. Moscow State Universiry Publishers, Moscow (1989) (in Russian)

    Google Scholar 

  76. Moshkov, M.J.: On complexity of algorithms for construction of tests for diagnosis constant faults on inputs of combinatorial circuits. In: Proceedings of the Ninth All-Union Conference Problems of Theoretical Cybernetics, Part I (1), Volgograd, Russia, p. 81 (1990) (in Russian)

    Google Scholar 

  77. Moshkov, M.J.: Decision trees with quasilinear checks. Trudy IM SO RAN 27, 108–141 (1994) (in Russian)

    MathSciNet  Google Scholar 

  78. Moshkov, M.J.: Optimization problems for decision trees. Fundamenta Informaticae 21, 391–401 (1994)

    MATH  MathSciNet  Google Scholar 

  79. Moshkov, M.J.: Decision Trees. Theory and Applications. Nizhny Novgorod University Publishers, Nizhny Novgorod (1994) (in Russian)

    Google Scholar 

  80. Moshkov, M.J.: About the depth of decision trees computing Boolean functions. Fundamenta Informaticae 22, 203–215 (1995)

    MATH  MathSciNet  Google Scholar 

  81. Moshkov, M.J.: Two approaches to investigation of deterministic and nondeterministic decision tree complexity. In: Proceedings of the World Conference on the Fundamentals of AI. Paris, France, pp. 275–280 (1995)

    Google Scholar 

  82. Moshkov, M.J.: Complexity of decision trees for regular language word recognition. In: Preproceedings of the Second International Conference Developments in Language Theory, Magdeburg, Germany (1995)

    Google Scholar 

  83. Moshkov, M.J.: Comparative analysis of complexity of deterministic and nondeterministic decision trees. In: Local Approach. Actual Problems of Modern Mathematics 1, pp. 109–113. NII MIOO NGU Publishers, Novosibirsk (1995) (in Russian)

    Google Scholar 

  84. Moshkov, M.J.: Comparative analysis of deterministic and nondeterministic decision tree complexity. Global approach. Fundamenta Informaticae 25, 201–214 (1996)

    MATH  MathSciNet  Google Scholar 

  85. Moshkov, M.J.: Lower bounds on time complexity of deterministic conditional tests. Discrete Mathematics 8(3), 98–110 (1996) (in Russian)

    MathSciNet  Google Scholar 

  86. Moshkov, M.J.: On the depth of decision trees over arbitrary check system. In: Proceedings of the Eleventh International Conference Problems of Theoretical Cybernetics, Uljanovsk, Russia, pp. 146–147 (1996) (in Russian)

    Google Scholar 

  87. Moshkov, M.J.: On the depth of decision trees over infinite information systems. In: Proceedings of the Congress Information Processing and Management of Uncertainty in Knowledge-based Systems, Granada, Spain, pp. 885–886 (1996)

    Google Scholar 

  88. Moshkov, M.J.: On global Shannon functions of two-valued information systems. In: Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery, Tokyo, Japan, pp. 142–143 (1996)

    Google Scholar 

  89. Moshkov, M.J.: Bounds on the depth of decision trees that compute Boolean functions. Russian Academy of Sciences Doklady 350(1), 22–24 (1996) (in Russian); English translation: Dokl. Math. 54(2), 662–664 (1996)

    MathSciNet  Google Scholar 

  90. Moshkov, M.J.: Local and global approaches to comparative analysis of complexity of deterministic and nondeterministic decision trees. In: Actual Problems of Modern Mathematics, vol. 2, pp. 110–118. NII MIOO NGU Publishers, Novosibirsk (1996) (in Russian)

    Google Scholar 

  91. Moshkov, M.J.: Diagnosis of constant faults of circuits. In: Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery, Tokyo, Japan, pp. 325–327 (1996)

    Google Scholar 

  92. Moshkov, M.J.: Some bounds on minimal decision tree depth. Fundamenta Informaticae 27, 197–203 (1996)

    MATH  MathSciNet  Google Scholar 

  93. Moshkov, M.J.: Unimprovable upper bounds on complexity of decision trees over information systems. Foundations of Computing and Decision Sciences 21(4), 219–231 (1996)

    MATH  MathSciNet  Google Scholar 

  94. Moshkov, M.J.: Optimization of decision trees. Intellectual Systems 1(1-4), 199–204 (1996) (in Russian)

    Google Scholar 

  95. Moshkov, M.J.: On complexity of decision trees over infinite information systems. In: Proceedings of the Third Joint Conference on Information Systems, USA, Duke University, pp. 353–354 (1997)

    Google Scholar 

  96. Moshkov, M.J.: Comparative analysis of time complexity of deterministic and nondeterministic tree-programs. In: Actual Problems of Modern Mathematics, vol. 3, pp. 117–124. NII MIOO NGU Publishers, Novosibirsk (1997) (in Russian)

    Google Scholar 

  97. Moshkov, M.J.: Algorithms for constructing of decision trees. In: Komorowski, J., Żytkow, J.M. (eds.) PKDD 1997. LNCS (LNAI), vol. 1263, pp. 335–342. Springer, Heidelberg (1997)

    Google Scholar 

  98. Moshkov, M.J.: Unimprovable upper bounds on time complexity of decision trees. Fundamenta Informaticae 31(2), 157–184 (1997)

    MATH  MathSciNet  Google Scholar 

  99. Moshkov, M.J.: Rough analysis of tree-programs. In: Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, pp. 231–235 (1997)

    Google Scholar 

  100. Moshkov, M.J.: Complexity of deterministic and nondeterministic decision trees for regular language word recognition. In: Proceedings of the Third International Conference Developments in Language Theory, Thessaloniki, Greece, pp. 343–349 (1997)

    Google Scholar 

  101. Moshkov, M.J.: Some relationships between decision trees and decision rule systems. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 499–505. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  102. Moshkov, M.J.: On time complexity of decision trees. In: Polkowski, L., Skowron, A. (eds.) Rough Sets in Knowledge Discovery 1. Methodology and Applications (Studies in Fuzziness and Soft Computing 18), pp. 160–191. Phisica-Verlag/A Springer- Verlag Company, Heidelberg (1998)

    Google Scholar 

  103. Moshkov, M.J.: On the depth of decision trees. Russian Academy of Sciences Doklady 358(1), 26 (1998) (in Russian)

    MathSciNet  Google Scholar 

  104. Moshkov, M.J.: On time complexity of decision trees. In: Proceedings of International Siberian Conference on Operations Research, Novosibirsk, Russia, pp. 28–31 (1998) (in Russian)

    Google Scholar 

  105. Moshkov, M.J.: Bounds on depth of decision trees over finite two-valued check systems. In: Yablonskii, S.V. (ed.) Mathematical Problems of Cybernetics, vol. 7, pp. 162–168. Nauka Publishers, Moscow (1998) (in Russian)

    Google Scholar 

  106. Moshkov, M.J.: Local approach to construction of decision trees. In: Pal, S.K., Skowron, A. (eds.) Rough-Fuzzy Hybridization: A New Trend in Decision-Making, pp. 163–176. Springer, Singapore (1999)

    Google Scholar 

  107. Moshkov, M.J.: On complexity of deterministic and nondeterministic decision trees. In: Proceedings of the Twelfth International Conference Problems of Theoretical Cybernetics, Part 2, Nizhny Novgorod, Russia, p. 164 (1999) (in Russian)

    Google Scholar 

  108. Moshkov, M.J.: Time complexity of decision trees. In: Proceedings of the Ninth Interstates Workshop Design and Complexity of Control Systems, Nizhny Novgorod, Russia, pp. 52–62 (1999) (in Russian)

    Google Scholar 

  109. Moshkov, M.J.: Deterministic and nondeterministic decision trees for rough computing. Fundamenta Informaticae 41(3), 301–311 (2000)

    MATH  MathSciNet  Google Scholar 

  110. Moshkov, M.J.: Decision trees for regular language word recognition. Fundamenta Informaticae 41(4), 449–461 (2000)

    MATH  MathSciNet  Google Scholar 

  111. Moshkov, M.J.: About papers of R.G. Nigmatullin on approximate algorithms for solving of discrete extremal problems. Discrete Analysis and Operations Research 7(1), 6–17 (2000) (in Russian)

    MATH  MathSciNet  Google Scholar 

  112. Moshkov, M.J.: Classification of infinite information systems. In: Ziarko, W.P., Yao, Y. (eds.) RSCTC 2000. LNCS (LNAI), vol. 2005, pp. 167–171. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  113. Moshkov, M.J.: On time and space complexity of deterministic and nondeterministic decision trees. In: Proceedings of the Eighth International Conference Information Processing and Management of Uncertainty in Knowledge-based Systems, Madrid, Spain, vol. 3, pp. 1932–1936 (2000)

    Google Scholar 

  114. Moshkov, M.J.: On complexity of decision trees over infinite check systems. In: Proceedings of the Fourth International Conference on Discrete Models in Control System Theory, Krasnovidovo, Russia, pp. 83–86 (2000) (in Russian)

    Google Scholar 

  115. Moshkov, M.J.: Diagnosis of constant faults in circuits. In: Lupanov, O.B. (ed.) Mathematical Problems of Cybernetics, vol. 9, pp. 79–100. Nauka Publishers, Moscow (2000) (in Russian)

    Google Scholar 

  116. Moshkov, M.J.: Elements of Mathematical Theory of Tests with Applications to Problems of Discrete Optimization. Nizhny Novgorod University Publishers, Nizhny Novgorod (2001) (in Russian)

    Google Scholar 

  117. Moshkov, M.J.: On space and time complexity of decision trees. In: Discrete Mathematics and its Applications. Collection of Lectures for Youth Scientific Schools on Discrete Mathematics and its Applications, vol. 2, Center for Applied Investigations of Faculty of Mathematics and Mechanics, Moscow State University, Moscow, pp. 35–40 (2001) (in Russian)

    Google Scholar 

  118. Moshkov, M.J.: Classification of infinite check systems depending on complexity of decision trees and decision rule systems. In: Proceedings of the Eleventh Interstates Workshop Design and Complexity of Control Systems, Part 1, Nizhny Novgorod, Russia, pp. 109–116 (2001) (in Russian)

    Google Scholar 

  119. Moshkov, M.J.: Test theory and problems of machine learning. In: Proceedings of the International School-Seminar on Discrete Mathematics and Mathematical Cybernetics, Ratmino, Russia, pp. 6–10 (2001)

    Google Scholar 

  120. Moshkov, M.J.: On transformation of decision rule systems into decision trees. In: Proceedings of the Seventh International Workshop Discrete Mathematics and its Applications, Part 1, Moscow, Russia, pp. 21–26 (2001) (in Russian)

    Google Scholar 

  121. Moshkov, M.J.: On deciphering of monotone 0-1 function defined on tree with root. In: Proceedings of the Twelfth International Workshop Design and Complexity of Control Systems, Part 2, Penza, Russia, pp. 157–160 (2001) (in Russian)

    Google Scholar 

  122. Moshkov, M.J.: On decision trees for (1,2)-Bayesian networks. Fundamenta Informaticae 50(1), 57–76 (2002)

    MATH  MathSciNet  Google Scholar 

  123. Moshkov, M.J.: On compressible information systems. In: Alpigini, J.J., Peters, J.F., Skowron, A., Zhong, N. (eds.) RSCTC 2002. LNCS (LNAI), vol. 2475, pp. 156–160. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  124. Moshkov, M.J.: On closed classes of machine learning problems. In: Proceedings of the Thirteenth International Conference Problems of Theoretical Cybernetics, Part 2, Kazan, Russia, p. 128 (2002) (in Russian)

    Google Scholar 

  125. Moshkov, M.J.: Greedy algorithm for set cover in context of knowledge discovery problems. In: Proceedings of the International Workshop on Rough Sets in Knowledge Discovery and Soft Computing (ETAPS 2003 Satellite Event), Warsaw, Poland. Electronic Notes in Theoretical Computer Science, vol. 82(4) (2003), http://www.elsevier.nl/locate/entcs/volume82.html

  126. Moshkov, M.J.: Approximate algorithm for minimization of decision tree depth. In: Wang, G., Liu, Q., Yao, Y., Skowron, A. (eds.) RSFDGrC 2003. LNCS (LNAI), vol. 2639, pp. 611–614. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  127. Moshkov, M.J.: Classification of infinite information systems depending on complexity of decision trees and decision rule systems. Fundamenta Informaticae 54(4), 345–368 (2003)

    MATH  MathSciNet  Google Scholar 

  128. Moshkov, M.J.: Compressible infinite information systems. Fundamenta Informaticae 55(1), 51–61 (2003)

    MATH  MathSciNet  Google Scholar 

  129. Moshkov, M.J., Chikalov, I.V.: On the average depth of decision trees over information systems. In: Proceedings of the Fourth European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, vol. 1, pp. 220–222 (1996)

    Google Scholar 

  130. Moshkov, M.J., Chikalov, I.V.: Upper bound on average depth of decision trees over information systems. In: Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery, Tokyo, Japan, pp. 139–141 (1996)

    Google Scholar 

  131. Moshkov, M.J., Chikalov, I.V.: Bounds on average weighted depth of decision trees. Fundamenta Informaticae 31(2), 145–156 (1997)

    MATH  MathSciNet  Google Scholar 

  132. Moshkov, M.J., Chikalov, I.V.: Bounds on average depth of decision trees. In: Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, pp. 226–230 (1997)

    Google Scholar 

  133. Moshkov, M.J., Chikalov, I.V.: On effective algorithms for construction of decision trees. In: Proceedings of the Twelfth International Conference Problems of Theoretical Cybernetics, Part 2, Nizhny Novgorod, Russia, p. 165 (1999) (in Russian)

    Google Scholar 

  134. Moshkov, M.J., Chikalov, I.V.: On algorithm for constructing of decision trees with minimal depth. Fundamenta Informaticae 41(3), 295–299 (2000)

    MATH  MathSciNet  Google Scholar 

  135. Moshkov, M.J., Chikalov, I.V.: On complexity of construction of minimal tests and minimal conditional tests for some class of problems. In: Proceedings of the Thirteenth International Workshop Design and Complexity of Control Systems, Part 2, Penza, Russia, pp. 165–168 (2002) (in Russian)

    Google Scholar 

  136. Moshkov, M.J., Chikalov, I.V.: Sequential optimization of decision trees relatively different complexity measures. In: Proceedings of the Sixth International Conference Soft Computing and Distributed Processing, Rzeszow, Poland, pp. 53–56 (2002)

    Google Scholar 

  137. Moshkov, M.J., Moshkova, A.M.: Optimal bases for some closed classes of Boolean functions. In: Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, pp. 1643–1647 (1997)

    Google Scholar 

  138. Moshkova, A.M.: Diagnosis of retaining faults of combinatorial circuits. Bulletin of Nizhny Novgorod State University. Mathematical Simulation and Optimal Control 2, 204–233 (1998) (in Russian)

    Google Scholar 

  139. Moshkova, A.M.: On diagnosis of retaining faults in circuits. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 513–516. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  140. Moshkova, A.M.: On time complexity of “retaining” fault diagnosis in circuits. In: Proceedings of the Eighth International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Madrid, Spain, vol. 1, pp. 372–375 (2000)

    Google Scholar 

  141. Müller, W., Wysotzki, F.: Automatic construction of decision trees for classification. Annals of Operations Research 52, 231–247 (1994)

    Article  MATH  Google Scholar 

  142. Murthy, S.K., Kasif, S., Salzberg, S.: A system for induction of oblique decision trees. Journal of Artificial Intelligence Research 2, 1–33 (1994)

    MATH  Google Scholar 

  143. Nguyen, H.S.: From optimal hyperplanes to optimal decision trees. Fundamenta Informaticae 34(1-2), 145–174 (1998)

    MATH  MathSciNet  Google Scholar 

  144. Nguyen, H.S.: On efficient handling of continuous attributes in large data bases. Fundamenta Informaticae 48(1), 61–81 (2001)

    MATH  MathSciNet  Google Scholar 

  145. Nguyen, H.S., Nguyen, H.H.: Discretization methods in data mining. In: Polkowski, L., Skowron, A. (eds.) Rough Sets in Knowledge Discovery 1. Methodology and Applications (Studies in Fuzziness and Soft Computing 18), pp. 451–482. Phisica- Verlag/A Springer-Verlag Company, Heidelberg 1998)

    Google Scholar 

  146. Nguyen, S.H., Nguyen, H.S.: Pattern extraction from data. Fundamenta Informaticae 34(1-2), 129–144 (1998)

    MATH  MathSciNet  Google Scholar 

  147. Nguyen, H.S., Slezak, D.: Approximate reducts and association rules – correspondence and complexity results. In: Zhong, N., Skowron, A., Ohsuga, S. (eds.) RSFDGrC 1999. LNCS (LNAI), vol. 1711, pp. 137–145. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  148. Nigmatullin, R.G.: Method of steepest descent in problems on cover. In: Memoirs of Symposium Problems of Precision and Efficiency of Computing Algorithms, Kiev, USSR, vol. 5, pp. 116–126 (1969) (in Russian)

    Google Scholar 

  149. Okolnishnikova, E.A.: Lower bounds on complexity of realization of characteristic functions of binary codes by branching programs. In: Korshunov, A.D. (ed.) Methods of Discrete Analysis, vol. 51, pp. 61–83. IM SO AN USSR Publishers, Novosibirsk (1991) (in Russian)

    Google Scholar 

  150. Pal, S.K., Polkowski, L., Skowron, A. (eds.): Rough-Neural Computing. Techniques for Computing with Words. Springer Verlag series in Cognitive Technologies, Berlin (2003)

    Google Scholar 

  151. Parchomenko, P.P.: Theory of questionnaires. Automation and Telemechanics 4, 140–159 (1970) (in Russian)

    Google Scholar 

  152. Parchomenko, P.P., Sogomonyan, E.S.: Fundamentals of Technical Diagnosis. Energoizdat Publishers, Moscow (1981) (in Russian)

    Google Scholar 

  153. Pawlak, Z.: Information Systems – Theoretical Foundations. PWN, Warsaw (1981) (in Polish)

    Google Scholar 

  154. Pawlak, Z.: Rough sets. International J. Comp. Inform. Science 11, 341–356 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  155. Pawlak, Z.: Rough classification. Report of the Computing Center of the Polish Academy of Sciences 506 (1983)

    Google Scholar 

  156. Pawlak, Z.: Rough sets and fuzzy sets. Fuzzy Sets and Systems 17, 99–102 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  157. Pawlak, Z.: Rough sets and decision tables. In: Skowron, A. (ed.) SCT 1984. LNCS, vol. 208, pp. 186–196. Springer, Heidelberg (1985)

    Google Scholar 

  158. Pawlak, Z.: On rough dependency of attributes in information systems. Bull. Polish Acad. Sci. Tech. 33, 551–599 (1985)

    MATH  MathSciNet  Google Scholar 

  159. Pawlak, Z.: On decision tables. Bull. Polish Acad. Sci. Tech. 34, 553–572 (1986)

    Google Scholar 

  160. Pawlak, Z.: Rough logic. Bull. Polish Acad. Sci. Tech. 35, 253–258 (1987)

    MATH  MathSciNet  Google Scholar 

  161. Pawlak, Z.: Decision tables – a rough set approach. Bull. of EATCS 33, 85–96 (1987)

    MATH  Google Scholar 

  162. Pawlak, Z.: Rough Sets – Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)

    MATH  Google Scholar 

  163. Pearl, J.: Probabilistic Inference in Intelligent Systems. Morgan Kaufman, San Francisco (1988)

    Google Scholar 

  164. Peters, J.F., Skowron, A., Stepaniuk, J., Ramanna, S.: Towards an ontology of approximate reason. Fundamenta Informaticae 51(1-2), 157–173 (2002)

    MATH  MathSciNet  Google Scholar 

  165. Peters, J.F., Skowron, A., Synak, P., Ramanna, S.: Rough sets and information granulation. In: De Baets, B., Kaynak, O., Bilgiç, T. (eds.) IFSA 2003. LNCS, vol. 2715, pp. 370–377. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  166. Picard, C.F.: Theorie des Questionnaires. Gauthier-Villars, Paris (1965)

    MATH  Google Scholar 

  167. Picard, C.F.: Graphes et Questionnaires, vol. 1, 2. Gauthier-Villars, Paris (1972)

    Google Scholar 

  168. Polkowski, L.: Rough Sets. Mathematical Foundations (Advances in Soft Computing). Physica-Verlag, Heidelberg (2002)

    MATH  Google Scholar 

  169. Polkowski, L., Lin, T.Y., Tsumoto, S. (eds.): Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems. Studies in Fuzziness and Soft Computing, vol. 56. Phisica-Verlag/A Springer-Verlag Company, Heidelberg 2000)

    Google Scholar 

  170. Pollack, S.L.: Decision Tables: Theory and Practice. J. Wiley & Sons Inc., Chichester (1971)

    Google Scholar 

  171. Post, E.: Introduction to a general theory of elementary propositions. Amer. J. Math. 43, 163–185 (1921)

    Article  MATH  MathSciNet  Google Scholar 

  172. Post, E.: Two-valued iterative systems of mathematical logic. In: Annals of Math. Studies, vol. 5. Princeton Univ. Press, Princeton (1941)

    Google Scholar 

  173. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1985)

    Google Scholar 

  174. Quinlan, J.R.: Discovering rules by induction from large collections of examples. In: Michie, D. (ed.) Experts Systems in the Microelectronic Age. Edinburg University Press (1979)

    Google Scholar 

  175. Quinlan, J.R.: Induction of decision trees. Machine Learning 1(1), 81–106 (1986)

    Google Scholar 

  176. Quinlan, J.R.: Generating production rules from decision trees. In: Proc. of the Tenth Int. Joint Conf. on AI, pp. 304–307 (1987)

    Google Scholar 

  177. Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo (1993)

    Google Scholar 

  178. Redkin, N.P.: Reliability and Diagnosis of Circuits. Moscow University Publishers, Moscow (1992) (in Russian)

    Google Scholar 

  179. Rissanen, J.: Modeling by shortest data description. Automatica 14, 465–471 (1978)

    Article  MATH  Google Scholar 

  180. Roth, J.P.: Diagnosis of automata failures: a calculus and method. Journal Research and Development, 278–291 (1966)

    Google Scholar 

  181. Sapozhenko, A.A.: On a proof of upper bound on complexity of minimal disjunctive normal form for almost all functions. In: Proceedings of the First All-Union Conference Problems of Theoretical Cybernetics, Novosibirsk, USSR, p. 103 (1969)

    Google Scholar 

  182. Sauer, N.: On the density of families of sets. J. of Combinatorial Theory (A) 13, 145–147 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  183. Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. of Mathematics 41, 241–261 (1972)

    Google Scholar 

  184. Shevtchenko, V.I.: On complexity of diagnosis of one type of faults in combinatorial circuits by conditional tests. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods in Applied Mathematics, pp. 86–97. Gorky University Publishers, Gorky (1988) (in Russian)

    Google Scholar 

  185. Shevtchenko, V.I.: On complexity of diagnosis of faults of the type “⊕” in combinatorial circuits. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis, pp. 129–140. Gorky University Publishers, Gorky (1989) (in Russian)

    Google Scholar 

  186. Shevtchenko, V.I.: On complexity of diagnosis of faults of types “0”, “1”, “&” and “∨” in combinatorial circuits. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods and its Application, pp. 125–150. Gorky University Publishers, Gorky (1990)

    Google Scholar 

  187. Shevtchenko, V.I.: On depth of conditional tests for diagnosis of “negation” type faults in circuits. Siberian Journal on Operations Research 1, 63–74 (1994) (in Russian)

    Google Scholar 

  188. Shevtchenko, V.I.: On the depth of decision trees for diagnosing faults in circuits. In: Soft Computing (Third International Workshop on Rough Sets and Soft Computing), pp. 200–203. The Society for Computer Simulation, San Diego (1995)

    Google Scholar 

  189. Shevtchenko, V.I.: On the depth of decision trees for control faults in circuits. In: Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery, Tokyo, Japan, pp. 328–330 (1996)

    Google Scholar 

  190. Shevtchenko, V.I.: On complexity of conditional tests for diagnosis of circuits. Intellectual Systems 1(1–4), 247–251 (1996) (in Russian)

    Google Scholar 

  191. Shevtchenko, V.I.: On the depth of decision trees for diagnosing of nonelementary faults in circuits. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol. 1424, pp. 517–520. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  192. Shevtchenko, V.I., Moshkov, M.J., Moshkova, A.M.: Effective methods for diagnosis of faults in circuits. In: Proceedings of the Eleventh Interstates Workshop Design and Complexity of Control Systems, Part 2, Nizhny Novgorod, Russia, pp. 228–238 (2001) (in Russian)

    Google Scholar 

  193. Skowron, A.: Rough sets in KDD. In: Proceedings of the 16-th World Computer Congress (IFIP 2000), Beijing, China, pp. 1–14 (2000)

    Google Scholar 

  194. Skowron, A., Pal, S.K. (eds.): Special issue Rough sets, pattern recognition and data mining. Pattern Recognition Letters 24(6), 829–933 (2003)

    Article  Google Scholar 

  195. Skowron, A., Pawlak, Z., Komorowski, J., Polkowski, L.: A rough set perspective on data and knowledge. In: Kloesgen, W., Żytkow, J. (eds.) Handbook of KDD, pp. 134–149. Oxford University Press, Oxford (2002)

    Google Scholar 

  196. Skowron, A., Polkowski, L.: Synthesis of decision systems from data tables. In: Lin, T.Y., Cercone, N. (eds.) Rough Sets and Data Mining: Analysis for Imprecise Data, pp. 259–300. Kluwer Academic Publishers, Boston (1997)

    Google Scholar 

  197. Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: Slowinski, R. (ed.) Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, pp. 331–362. Kluwer Academic Publishers, Dordrecht (1992)

    Google Scholar 

  198. Skowron, A., Swiniarski, R.: Information granulation and pattern recognition. In: Pal, S.K., Polkowski, L., Skowron, A. (eds.) Rough-Neural Computing. Techniques for Computing with Words. Springer Verlag series in Cognitive Technologies, Berlin, pp. 599–636 (2003)

    Google Scholar 

  199. Slezak, D.: Approximate decision reducts. Ph.D. thesis. Warsaw University (2002) (in Polish)

    Google Scholar 

  200. Slezak, D.: Approximate Markov boundaries and bayesian networks: Rough set approach. In: Inuiguchi, M., Tsumoto, S., Hirano, S. (eds.) Rough Set Theory and Granular Computing. Studies in Fuzziness and Soft Computing, vol. 125, pp. 109–121. Phisica- Verlag, A Springer-Verlag Company, Heidelberg (2003)

    Google Scholar 

  201. Slowinski, R. (ed.): Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory. Kluwer Academic Publishers, Dordrecht (1992)

    MATH  Google Scholar 

  202. Soloviev, N.A.: On certain property of tables with uncancellable tests of equal length. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol. 12, pp. 91–95. Nauka Publishers, Novosibirsk (1968) (in Russian)

    Google Scholar 

  203. Soloviev, N.A.: Tests (Theory, Construction, Applications). Nauka Publishers, Novosibirsk (1978) (in Russian)

    Google Scholar 

  204. Steele, J.M., Yao, A.C.: Lower bounds for algebraic decision trees. J. of Algorithms 3, 1–8 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  205. Swiniarski, R., Skowron, A.: Rough set methods in feature selection and recognition. Pattern Recognition Letters 24, 833–849 (2003)

    Article  MATH  Google Scholar 

  206. Tarasova, V.P.: Opponent Strategy Method in Optimal Search Problems. Moscow University Publishers, Moscow (1988) (in Russian)

    Google Scholar 

  207. Tarski, A.: Arithmetical classes and types of mathematical systems, Mathematical aspects of arithmetical classes and types, Arithmetical classes and types of Boolean algebras, Arithmetical classes and types of algebraically closed and real closed fields. Bull. Amer. Math. Soc. 55, 63–64 (1949)

    Google Scholar 

  208. Ufnarovskii, V.A.: Criterion of growth of graphs and algebras defined by words. Mathematical Notes 31(3), 465–472 (1982) (in Russian)

    MathSciNet  Google Scholar 

  209. Ugolnikov, A.B.: On depth and polynomial equivalence of formulas for closed classes of binary logic. Mathematical Notes 42(4), 603–612 (1987) (in Russian)

    MathSciNet  Google Scholar 

  210. Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16(2), 264–280 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  211. Vasilevsky, M.P.: On recognition of faults of automata. Cybernetics 4, 98–108 (1973) (in Russian)

    Google Scholar 

  212. Vasilevsky, M.P.: On deciphering of automata. Cybernetics 2, 19–23 (1974) (in Russian)

    Google Scholar 

  213. Wegener, I.: The Complexity of Boolean Functions. John Wiley and Sons/B.G. Teubner, Stuttgart (1987)

    MATH  Google Scholar 

  214. Yablonskii, S.V.: Tests. Encyklopaedia Kybernetiki. In: Glushkov, V.M. (ed.) Main Editorial Staff of Ukrainian Soviet Encyklopaedia, Kiev, pp. 431–432 (1975) (in Russian)

    Google Scholar 

  215. Yablonskii, S.V.: Some problems of reliability and diagnosis in control systems. In: Yablonskii, S.V. (ed.) Mathematical Problems of Cybernetics, vol. 1, pp. 5–25. Nauka Publishers, Moscow (1988) (in Russian)

    Google Scholar 

  216. Yablonskii, S.V., Chegis, I.A.: On tests for electric circuits. UMN 10(4), 182–184 (1955) (in Russian)

    Google Scholar 

  217. Yablonskii, S.V., Gavrilov, G.P., Kudriavtzev, V.B.: Functions of Algebra of Logic and Classes of Post. Nauka Publishers, Moscow (1966) (in Russian)

    Google Scholar 

  218. Yao, A.: Algebraic decision trees and Euler characteristics. In: Proceedings IEEE FOCS, pp. 268–277 (1992)

    Google Scholar 

  219. Yao, A.: Decision tree complexity and Betti numbers. In: Proceedings ACM STOC, pp. 615–624 (1994)

    Google Scholar 

  220. Zhuravlev, J.I.: On a class of partial Boolean functions. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol. 2, pp. 23–27. IM SO AN USSR Publishers, Novosibirsk (1964) (in Russian)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computing Mathematics and Cybernetics, Nizhny Novgorod State University, 23, Gagarina Ave., Nizhny Novgorod, 603950, Russia

    Mikhail Ju. Moshkov

  2. Institute of Computer Science, University of Silesia, 39, Bȩdzińska St., Sosnowiec, 41-200, Poland

    Mikhail Ju. Moshkov

Authors
  1. Mikhail Ju. Moshkov
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Manitoba, R3T 5V6, Winnipeg, Manitoba, Canada

    James F. Peters

  2. Institute of Mathematics, Warsaw University, Banacha 2, 02-097, Warsaw, Poland

    Andrzej Skowron

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Moshkov, M.J. (2005). Time Complexity of Decision Trees. In: Peters, J.F., Skowron, A. (eds) Transactions on Rough Sets III. Lecture Notes in Computer Science, vol 3400. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11427834_12

Download citation

  • DOI: https://doi.org/10.1007/11427834_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-25998-5

  • Online ISBN: 978-3-540-31850-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation