{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T19:00:12Z","timestamp":1774551612099,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":220,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540259985","type":"print"},{"value":"9783540318507","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11427834_12","type":"book-chapter","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T16:11:14Z","timestamp":1277914274000},"page":"244-459","source":"Crossref","is-referenced-by-count":79,"title":["Time Complexity of Decision Trees"],"prefix":"10.1007","author":[{"given":"Mikhail Ju.","family":"Moshkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Ahlswede, R., Wegener, I.: Suchprobleme. B.G. Teubner, Stuttgart (1979)","DOI":"10.1007\/978-3-322-91203-9"},{"key":"12_CR2","unstructured":"Alexeyev, V.E.: On entropy of two-dimensional fragmentary closed languages. In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods and its Application, pp. 5\u201313. Gorky University Publishers, Gorky (1987) (in Russian)"},{"issue":"4","key":"12_CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02(4), 319\u2013342 (1988)","journal-title":"Machine Learning"},{"issue":"1","key":"12_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/PGEC.1966.264376","volume":"15","author":"D.B. Armstrong","year":"1966","unstructured":"Armstrong, D.B.: On finding of nearly minimal set of fault detection tests for combinatorial logic nets. IEEE Trans. on Elec. Comp.\u00a0EC-15(1), 66\u201373 (1966)","journal-title":"IEEE Trans. on Elec. Comp."},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Bazan, J., Nguyen, H., Son, N.S., Hoa, S.P., Wr\u00f3blewski, 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\u201388. Phisica-Verlag\/A Springer-Verlag Company (2000)","DOI":"10.1007\/978-3-7908-1840-6_3"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of 15th ACM Annual Symp. on Theory of Comput., pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"issue":"4","key":"12_CR7","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM\u00a036(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"key":"12_CR8","first-page":"45","volume":"9","author":"V.A. Bondarenko","year":"1983","unstructured":"Bondarenko, V.A.: Non-polynomial lower bound on complexity of traveling salesman problem in one class of algorithms. Automation and Telemechanics\u00a09, 45\u201350 (1983) (in Russian)","journal-title":"Automation and Telemechanics"},{"issue":"1","key":"12_CR9","first-page":"22","volume":"328","author":"V.A. Bondarenko","year":"1993","unstructured":"Bondarenko, V.A.: Complexity bounds for combinatorial optimization problems in one class of algorithms. Russian Academy of Sciences Doklady\u00a0328(1), 22\u201324 (1993) (in Russian)","journal-title":"Russian Academy of Sciences Doklady"},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.3233\/FI-1996-25103","volume":"25","author":"V.A. Bondarenko","year":"1996","unstructured":"Bondarenko, V.A., Yurov, S.V.: About a polyhedron of cubic graphs. Fundamenta Informaticae\u00a025, 35\u201338 (1996)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR11","volume-title":"Classification and Regression Trees","author":"L. Breiman","year":"1984","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Chapman and Hall, New York (1984)"},{"key":"12_CR12","first-page":"45","volume":"19","author":"C.E. Brodley","year":"1995","unstructured":"Brodley, C.E., Utgoff, P.E.: Multivariate decision trees. Machine Learning\u00a019, 45\u201377 (1995)","journal-title":"Machine Learning"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01889584","volume":"2","author":"W. Buntine","year":"1992","unstructured":"Buntine, W.: Learning classification trees. Statistics and Computing\u00a02, 63\u201373 (1992)","journal-title":"Statistics and Computing"},{"key":"12_CR14","first-page":"270","volume":"51","author":"I.A. Chegis","year":"1958","unstructured":"Chegis, I.A., Yablonskii, S.V.: Logical methods of electric circuit control. Trudy MIAN SSSR\u00a051, 270\u2013360 (1958) (in Russian)","journal-title":"Trudy MIAN SSSR"},{"key":"12_CR15","volume-title":"Linear Inequalities","author":"S.N. Chernikov","year":"1968","unstructured":"Chernikov, S.N.: Linear Inequalities. Nauka Publishers, Moscow (1968) (in Russian)"},{"key":"12_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/3-540-69115-4_69","volume-title":"Rough Sets and Current Trends in Computing","author":"I.V. Chikalov","year":"1998","unstructured":"Chikalov, I.V.: On decision trees with minimal average depth. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol.\u00a01424, pp. 506\u2013512. Springer, Heidelberg (1998)"},{"key":"12_CR17","unstructured":"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.\u00a02, pp. 1190\u20131194 (1998)"},{"key":"12_CR18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.3233\/FI-1999-39401","volume":"39","author":"I.V. Chikalov","year":"1999","unstructured":"Chikalov, I.V.: On average time complexity of decision trees and branching programs. Fundamenta Informaticae\u00a039, 337\u2013357 (1999)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR19","unstructured":"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.\u00a01, pp. 376\u2013379 (2000)"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"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\u2013111 (2000)","DOI":"10.1007\/3-540-45554-X_16"},{"key":"12_CR21","volume-title":"Readings in Machine Learning","year":"1990","unstructured":"Dietterich, T.G., Shavlik, J.W. (eds.): Readings in Machine Learning. Morgan Kaufmann, San Francisco (1990)"},{"issue":"2","key":"12_CR22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. Dobkin","year":"1976","unstructured":"Dobkin, D., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput.\u00a05(2), 181\u2013186 (1976)","journal-title":"SIAM J. Comput."},{"key":"12_CR23","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D. Dobkin","year":"1978","unstructured":"Dobkin, D., Lipton, R.J.: A lower bound of (1\/2)n2 on linear search programs for the knapsack problem. J. Comput. Syst. Sci.\u00a016, 413\u2013417 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D. Dobkin","year":"1979","unstructured":"Dobkin, D., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comput. Syst. Sci.\u00a018, 86\u201391 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR25","volume-title":"Pattern Recognition","author":"R.O. Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Recognition. Wiley, New York (2000)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"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\u00a02, 214\u2013223 (1998) (in Russian)","DOI":"10.1007\/3-540-69115-4_16"},{"issue":"1","key":"12_CR27","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/320954.320957","volume":"6","author":"B.D. Eldred","year":"1959","unstructured":"Eldred, B.D.: Test routines based on symbolic logic statements. J. ACM\u00a06(1), 33\u201336 (1959)","journal-title":"J. ACM"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"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\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"key":"12_CR29","unstructured":"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)"},{"key":"12_CR30","first-page":"3","volume-title":"Discrete Analysis","author":"R.S. Goldman","year":"1969","unstructured":"Goldman, R.S., Chipulis, V.P.: Diagnosis of iteration-free combinatorial circuits. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol.\u00a014, pp. 3\u201315. Nauka Publishers, Novosibirsk (1969) (in Russian)"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013265 (1995)","DOI":"10.1109\/SFCS.1995.492481"},{"key":"12_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-21606-5","volume-title":"The Elements of Statistical Learning: Data Mining, Inference, and Prediction","author":"T. Hastie","year":"2001","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, Berlin (2001)"},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1145\/225298.225311","volume-title":"Proceedings of the 8th Annual ACM Conference on Computational Learning Theory","author":"T. Heged\u00fcs","year":"1995","unstructured":"Heged\u00fcs, 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\u2013117. ACM, New York (1995)"},{"issue":"5","key":"12_CR34","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1145\/234752.234755","volume":"43","author":"L. Hellerstein","year":"1996","unstructured":"Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V.V., Wilkins, D.: How many queries are needed to learn? J. ACM\u00a043(5), 840\u2013862 (1996)","journal-title":"J. ACM"},{"key":"12_CR35","unstructured":"Humby, E.: Programs from Decision Tables. Macdonald, London, American Elsevier, New York (1973)"},{"key":"12_CR36","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00962072","volume":"2","author":"I.F. Imam","year":"1993","unstructured":"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\u00a02, 279\u2013304 (1993)","journal-title":"Journal of Intelligent Information Systems"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1007\/978-3-540-36473-3"},{"key":"12_CR38","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. System Sci."},{"key":"12_CR39","volume-title":"Learning in Graphical Models","year":"1999","unstructured":"Jordan, M.I. (ed.): Learning in Graphical Models. MIT Press, Cambridge (1999)"},{"key":"12_CR40","first-page":"173","volume":"1","author":"M.F. Karavai","year":"1973","unstructured":"Karavai, M.F.: Diagnosis of tree-like circuits in arbitrary basis. Automation and Telemechanics\u00a01, 173\u2013181 (1973) (in Russian)","journal-title":"Automation and Telemechanics"},{"key":"12_CR41","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-69115-4_16","volume-title":"Rough Sets and Current Trends in Computing","author":"A.N. Knyazev","year":"1998","unstructured":"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.\u00a01424, pp. 111\u2013114. Springer, Heidelberg (1998)"},{"key":"12_CR42","unstructured":"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)"},{"key":"12_CR43","unstructured":"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.\u00a01, pp. 1945\u20131948 (2000)"},{"key":"12_CR44","first-page":"3","volume-title":"Rough-Fuzzy Hybridization: A New Trend in Decision-Making","author":"J. Komorowski","year":"1999","unstructured":"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\u201398. Springer, Singapore (1999)"},{"key":"12_CR45","unstructured":"Kospanov, E.S.: On algorithm for construction of simple enough tests. Discrete Analysis, vol.\u00a08, pp. 43\u201347. Nauka Publishers, Novosibirsk (1966) (in Russian)"},{"key":"12_CR46","volume-title":"Higher Algebra","author":"A.G. Kurosh","year":"1975","unstructured":"Kurosh, A.G.: Higher Algebra, 11th edn. Nauka Publishers, Moscow (1975) (in Russian)","edition":"11"},{"key":"12_CR47","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1112\/jlms\/s2-45.2.377","volume":"45","author":"M.C. Laskowski","year":"1992","unstructured":"Laskowski, M.C.: Vapnik-Chervonenkis classes of definable sets. J. London Math. Society\u00a045, 377\u2013384 (1992)","journal-title":"J. London Math. Society"},{"key":"12_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5689-3","volume-title":"Feature Selection for Knowledge Discovery and Data Mining","author":"H. Liu","year":"1998","unstructured":"Liu, H., Motoda, H.: Feature Selection for Knowledge Discovery and Data Mining. Kluwer Academic Publishers, Boston (1998)"},{"key":"12_CR49","volume-title":"Feature Extraction, Construction and Selection: A Data Mining Approach","year":"1998","unstructured":"Liu, H., Motoda, H. (eds.): Feature Extraction, Construction and Selection: A Data Mining Approach. Kluwer Academic Publishers, Boston (1998)"},{"key":"12_CR50","first-page":"815","volume":"7","author":"W.-Y. Loh","year":"1997","unstructured":"Loh, W.-Y., Shih, Y.-S.: Split selection methods for classification trees. Statistica Sinica\u00a07, 815\u2013840 (1997)","journal-title":"Statistica Sinica"},{"issue":"5","key":"12_CR51","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"12_CR52","first-page":"103","volume-title":"Problems of Cybernetics","author":"C.A. Madatyan","year":"1970","unstructured":"Madatyan, C.A.: Complete test for iteration-free contact circuits. In: Yablonskii, S.V. (ed.) Problems of Cybernetics, vol.\u00a023, pp. 103\u2013118. Nauka Publishers, Moscow (1970) (in Russian)"},{"key":"12_CR53","volume-title":"Introduction into Coding Theory","author":"A.A. Markov","year":"1982","unstructured":"Markov, A.A.: Introduction into Coding Theory. Nauka Publishers, Moscow (1982)"},{"issue":"3","key":"12_CR54","first-page":"29","volume":"4","author":"A.A. Markov","year":"1992","unstructured":"Markov, A.A.: Circuit complexity of discrete optimization. Discrete Mathematics\u00a04(3), 29\u201346 (1992) (in Russian)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"12_CR55","first-page":"279","volume":"191","author":"J.V. Matiyasevich","year":"1970","unstructured":"Matiyasevich, J.V.: Diophantinity of enumerable sets. Academy of Sciences Doklady\u00a0191(2), 279\u2013382 (1970)","journal-title":"Academy of Sciences Doklady"},{"issue":"3","key":"12_CR56","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"Meyer auf der Heide, F.: A polynomial linear search algorithm for the ndimensional knapsack problem. J. ACM\u00a031(3), 668\u2013676 (1984)","journal-title":"J. ACM"},{"issue":"3","key":"12_CR57","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer auf der Heide","year":"1988","unstructured":"Meyer auf der Heide, F.: Fast algorithms for n-dimensional restrictions of hard problems. J. ACM\u00a035(3), 740\u2013747 (1988)","journal-title":"J. ACM"},{"key":"12_CR58","unstructured":"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\u2013172 (1973)"},{"key":"12_CR59","first-page":"129","volume-title":"Automata Studies","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F.: Gedanken-experiments on sequential machines. In: Shannon, C., McCarty, J. (eds.) Automata Studies, pp. 129\u2013153. Princeton University Press, Princeton (1956)"},{"issue":"6","key":"12_CR60","doi-asserted-by":"crossref","first-page":"442","DOI":"10.21136\/AM.1969.103254","volume":"14","author":"J. Moravek","year":"1969","unstructured":"Moravek, J.: On the complexity of discrete programming problems. Appl. Mat.\u00a014(6), 442\u2013474 (1969)","journal-title":"Appl. Mat."},{"issue":"6","key":"12_CR61","first-page":"498","volume":"8","author":"J. Moravek","year":"1972","unstructured":"Moravek, J.: A localization problems in geometry and complexity of discrete programming. Kybernetika\u00a08(6), 498\u2013516 (1972)","journal-title":"Kybernetika"},{"key":"12_CR62","first-page":"83","volume-title":"Combinatorial- Algebraic Methods in Applied Mathematics","author":"N.M. Morzhakov","year":"1985","unstructured":"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\u201398. Gorky University Publishers, Gorky (1985) (in Russian)"},{"key":"12_CR63","unstructured":"Morzhakov, N.M.: Bounds on complexity of construction of finite subsets of the set \u211d n . In: Markov, A.A. (ed.) Combinatorial-Algebraic Methods in Applied Mathematics, pp. 84\u2013106. Gorky University Publishers, Gorky (1986) (in Russian)"},{"key":"12_CR64","unstructured":"Morzhakov, N.M.: On possibilities of compression of finite subsets of the set \u211d n . In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods in Applied Mathematics, pp. 22\u201333. Gorky University Publishers, Gorky (1988) (in Russian)"},{"key":"12_CR65","first-page":"215","volume-title":"Mathematical Problems of Cybernetics","author":"N.M. Morzhakov","year":"1996","unstructured":"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.\u00a06, pp. 215\u2013238. Nauka Publishers, Moscow (1996) (in Russian)"},{"key":"12_CR66","first-page":"70","volume-title":"Combinatorial-Algebraic Methods in Applied Mathematics","author":"M.J. Moshkov","year":"1979","unstructured":"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\u201381. Gorky University Publishers, Gorky (1979) (in Russian)"},{"key":"12_CR67","first-page":"97","volume-title":"Combinatorial-Algebraic Methods in Applied Mathematics","author":"M.J. Moshkov","year":"1981","unstructured":"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\u2013109. Gorky University Publishers, Gorky (1981) (in Russian)"},{"issue":"3","key":"12_CR68","first-page":"550","volume":"265","author":"M.J. Moshkov","year":"1982","unstructured":"Moshkov, M.J.: On conditional tests. Academy of Sciences Doklady\u00a0265(3), 550\u2013552 (1982) (in Russian); English translation: Sov. Phys. Dokl.\u00a027, 528\u2013530 (1982)","journal-title":"Academy of Sciences Doklady"},{"key":"12_CR69","unstructured":"Moshkov, M.J.: Test approach to extremal combinatorial problems. Ph.D. thesis. Gorky University (1982) (in Russian)"},{"key":"12_CR70","first-page":"131","volume-title":"Problems of Cybernetics","author":"M.J. Moshkov","year":"1983","unstructured":"Moshkov, M.J.: Conditional tests. In: Yablonskii, S.V. (ed.) Problems of Cybernetics, vol.\u00a040, pp. 131\u2013170. Nauka Publishers, Moscow (1983) (in Russian)"},{"key":"12_CR71","first-page":"98","volume-title":"Combinatorial-Algebraic Methods in Applied Mathematics","author":"M.J. Moshkov","year":"1985","unstructured":"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\u2013119. Gorky University Publishers, Gorky (1985) (in Russian)"},{"key":"12_CR72","unstructured":"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)"},{"key":"12_CR73","first-page":"523","volume-title":"Mathematical Problems in Computation Theory, Banach Center Publications","author":"M.J. Moshkov","year":"1988","unstructured":"Moshkov, M.J.: On relationship of depth of deterministic and nondeterministic acyclic programs in the basis {x + y,x \u2212 y, 1; sign x}. In: Mathematical Problems in Computation Theory, Banach Center Publications, vol.\u00a021, pp. 523\u2013529. PWN, Polish Scientific Publishers, Warsaw (1988)"},{"key":"12_CR74","first-page":"78","volume-title":"Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis","author":"M.J. Moshkov","year":"1989","unstructured":"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\u201386. Gorky University Publishers, Gorky (1989) (in Russian)"},{"key":"12_CR75","first-page":"156","volume-title":"Proceedings of Workshop on Discrete Mathematics and its Applications","author":"M.J. Moshkov","year":"1989","unstructured":"Moshkov, M.J.: On minimization of object complexity. In: Proceedings of Workshop on Discrete Mathematics and its Applications, pp. 156\u2013161. Moscow State Universiry Publishers, Moscow (1989) (in Russian)"},{"key":"12_CR76","unstructured":"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)"},{"key":"12_CR77","first-page":"108","volume":"27","author":"M.J. Moshkov","year":"1994","unstructured":"Moshkov, M.J.: Decision trees with quasilinear checks. Trudy IM SO RAN\u00a027, 108\u2013141 (1994) (in Russian)","journal-title":"Trudy IM SO RAN"},{"key":"12_CR78","doi-asserted-by":"crossref","first-page":"391","DOI":"10.3233\/FI-1994-2147","volume":"21","author":"M.J. Moshkov","year":"1994","unstructured":"Moshkov, M.J.: Optimization problems for decision trees. Fundamenta Informaticae\u00a021, 391\u2013401 (1994)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR79","unstructured":"Moshkov, M.J.: Decision Trees. Theory and Applications. Nizhny Novgorod University Publishers, Nizhny Novgorod (1994) (in Russian)"},{"key":"12_CR80","doi-asserted-by":"crossref","first-page":"203","DOI":"10.3233\/FI-1995-2231","volume":"22","author":"M.J. Moshkov","year":"1995","unstructured":"Moshkov, M.J.: About the depth of decision trees computing Boolean functions. Fundamenta Informaticae\u00a022, 203\u2013215 (1995)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR81","unstructured":"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\u2013280 (1995)"},{"key":"12_CR82","unstructured":"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)"},{"key":"12_CR83","first-page":"109","volume-title":"Local Approach. Actual Problems of Modern Mathematics 1","author":"M.J. Moshkov","year":"1995","unstructured":"Moshkov, M.J.: Comparative analysis of complexity of deterministic and nondeterministic decision trees. In: Local Approach. Actual Problems of Modern Mathematics 1, pp. 109\u2013113. NII MIOO NGU Publishers, Novosibirsk (1995) (in Russian)"},{"key":"12_CR84","doi-asserted-by":"crossref","first-page":"201","DOI":"10.3233\/FI-1996-25205","volume":"25","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Comparative analysis of deterministic and nondeterministic decision tree complexity. Global approach. Fundamenta Informaticae\u00a025, 201\u2013214 (1996)","journal-title":"Global approach. Fundamenta Informaticae"},{"issue":"3","key":"12_CR85","first-page":"98","volume":"8","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Lower bounds on time complexity of deterministic conditional tests. Discrete Mathematics\u00a08(3), 98\u2013110 (1996) (in Russian)","journal-title":"Discrete Mathematics"},{"key":"12_CR86","unstructured":"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\u2013147 (1996) (in Russian)"},{"key":"12_CR87","unstructured":"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\u2013886 (1996)"},{"key":"12_CR88","unstructured":"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\u2013143 (1996)"},{"issue":"1","key":"12_CR89","first-page":"22","volume":"350","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Bounds on the depth of decision trees that compute Boolean functions. Russian Academy of Sciences Doklady\u00a0350(1), 22\u201324 (1996) (in Russian); English translation: Dokl. Math.\u00a054(2), 662\u2013664 (1996)","journal-title":"Russian Academy of Sciences Doklady"},{"key":"12_CR90","first-page":"110","volume-title":"Actual Problems of Modern Mathematics","author":"M.J. Moshkov","year":"1996","unstructured":"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.\u00a02, pp. 110\u2013118. NII MIOO NGU Publishers, Novosibirsk (1996) (in Russian)"},{"key":"12_CR91","unstructured":"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\u2013327 (1996)"},{"key":"12_CR92","doi-asserted-by":"crossref","first-page":"197","DOI":"10.3233\/FI-1996-272307","volume":"27","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Some bounds on minimal decision tree depth. Fundamenta Informaticae\u00a027, 197\u2013203 (1996)","journal-title":"Fundamenta Informaticae"},{"issue":"4","key":"12_CR93","first-page":"219","volume":"21","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Unimprovable upper bounds on complexity of decision trees over information systems. Foundations of Computing and Decision Sciences\u00a021(4), 219\u2013231 (1996)","journal-title":"Foundations of Computing and Decision Sciences"},{"issue":"1-4","key":"12_CR94","first-page":"199","volume":"1","author":"M.J. Moshkov","year":"1996","unstructured":"Moshkov, M.J.: Optimization of decision trees. Intellectual Systems\u00a01(1-4), 199\u2013204 (1996) (in Russian)","journal-title":"Intellectual Systems"},{"key":"12_CR95","unstructured":"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\u2013354 (1997)"},{"key":"12_CR96","first-page":"117","volume-title":"Actual Problems of Modern Mathematics","author":"M.J. Moshkov","year":"1997","unstructured":"Moshkov, M.J.: Comparative analysis of time complexity of deterministic and nondeterministic tree-programs. In: Actual Problems of Modern Mathematics, vol.\u00a03, pp. 117\u2013124. NII MIOO NGU Publishers, Novosibirsk (1997) (in Russian)"},{"key":"12_CR97","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/3-540-63223-9_132","volume-title":"Principles of Data Mining and Knowledge Discovery","author":"M.J. Moshkov","year":"1997","unstructured":"Moshkov, M.J.: Algorithms for constructing of decision trees. In: Komorowski, J., \u017bytkow, J.M. (eds.) PKDD 1997. LNCS (LNAI), vol.\u00a01263, pp. 335\u2013342. Springer, Heidelberg (1997)"},{"issue":"2","key":"12_CR98","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3233\/FI-1997-31205","volume":"31","author":"M.J. Moshkov","year":"1997","unstructured":"Moshkov, M.J.: Unimprovable upper bounds on time complexity of decision trees. Fundamenta Informaticae\u00a031(2), 157\u2013184 (1997)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR99","unstructured":"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\u2013235 (1997)"},{"key":"12_CR100","unstructured":"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\u2013349 (1997)"},{"key":"12_CR101","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/3-540-69115-4_68","volume-title":"Rough Sets and Current Trends in Computing","author":"M.J. Moshkov","year":"1998","unstructured":"Moshkov, M.J.: Some relationships between decision trees and decision rule systems. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol.\u00a01424, pp. 499\u2013505. Springer, Heidelberg (1998)"},{"key":"12_CR102","first-page":"160","volume-title":"Rough Sets in Knowledge Discovery 1. Methodology and Applications (Studies in Fuzziness and Soft Computing 18)","author":"M.J. Moshkov","year":"1998","unstructured":"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\u2013191. Phisica-Verlag\/A Springer- Verlag Company, Heidelberg (1998)"},{"issue":"1","key":"12_CR103","first-page":"26","volume":"358","author":"M.J. Moshkov","year":"1998","unstructured":"Moshkov, M.J.: On the depth of decision trees. Russian Academy of Sciences Doklady\u00a0358(1), 26 (1998) (in Russian)","journal-title":"Russian Academy of Sciences Doklady"},{"key":"12_CR104","doi-asserted-by":"crossref","unstructured":"Moshkov, M.J.: On time complexity of decision trees. In: Proceedings of International Siberian Conference on Operations Research, Novosibirsk, Russia, pp. 28\u201331 (1998) (in Russian)","DOI":"10.3233\/FI-1997-31205"},{"key":"12_CR105","first-page":"162","volume-title":"Mathematical Problems of Cybernetics","author":"M.J. Moshkov","year":"1998","unstructured":"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.\u00a07, pp. 162\u2013168. Nauka Publishers, Moscow (1998) (in Russian)"},{"key":"12_CR106","first-page":"163","volume-title":"Rough-Fuzzy Hybridization: A New Trend in Decision-Making","author":"M.J. Moshkov","year":"1999","unstructured":"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\u2013176. Springer, Singapore (1999)"},{"key":"12_CR107","unstructured":"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)"},{"key":"12_CR108","unstructured":"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\u201362 (1999) (in Russian)"},{"issue":"3","key":"12_CR109","doi-asserted-by":"crossref","first-page":"301","DOI":"10.3233\/FI-2000-41303","volume":"41","author":"M.J. Moshkov","year":"2000","unstructured":"Moshkov, M.J.: Deterministic and nondeterministic decision trees for rough computing. Fundamenta Informaticae\u00a041(3), 301\u2013311 (2000)","journal-title":"Fundamenta Informaticae"},{"issue":"4","key":"12_CR110","doi-asserted-by":"crossref","first-page":"449","DOI":"10.3233\/FI-2000-41405","volume":"41","author":"M.J. Moshkov","year":"2000","unstructured":"Moshkov, M.J.: Decision trees for regular language word recognition. Fundamenta Informaticae\u00a041(4), 449\u2013461 (2000)","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"12_CR111","first-page":"6","volume":"7","author":"M.J. Moshkov","year":"2000","unstructured":"Moshkov, M.J.: About papers of R.G. Nigmatullin on approximate algorithms for solving of discrete extremal problems. Discrete Analysis and Operations Research\u00a07(1), 6\u201317 (2000) (in Russian)","journal-title":"Discrete Analysis and Operations Research"},{"key":"12_CR112","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-45554-X_23","volume-title":"Rough Sets and Current Trends in Computing","author":"M.J.. Moshkov","year":"2001","unstructured":"Moshkov, M.J.: Classification of infinite information systems. In: Ziarko, W.P., Yao, Y. (eds.) RSCTC 2000. LNCS (LNAI), vol.\u00a02005, pp. 167\u2013171. Springer, Heidelberg (2001)"},{"key":"12_CR113","unstructured":"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.\u00a03, pp. 1932\u20131936 (2000)"},{"key":"12_CR114","unstructured":"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\u201386 (2000) (in Russian)"},{"key":"12_CR115","first-page":"79","volume-title":"Mathematical Problems of Cybernetics","author":"M.J. Moshkov","year":"2000","unstructured":"Moshkov, M.J.: Diagnosis of constant faults in circuits. In: Lupanov, O.B. (ed.) Mathematical Problems of Cybernetics, vol.\u00a09, pp. 79\u2013100. Nauka Publishers, Moscow (2000) (in Russian)"},{"key":"12_CR116","volume-title":"Elements of Mathematical Theory of Tests with Applications to Problems of Discrete Optimization","author":"M.J. Moshkov","year":"2001","unstructured":"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)"},{"key":"12_CR117","unstructured":"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.\u00a02, Center for Applied Investigations of Faculty of Mathematics and Mechanics, Moscow State University, Moscow, pp. 35\u201340 (2001) (in Russian)"},{"key":"12_CR118","unstructured":"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\u2013116 (2001) (in Russian)"},{"key":"12_CR119","unstructured":"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\u201310 (2001)"},{"key":"12_CR120","unstructured":"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\u201326 (2001) (in Russian)"},{"key":"12_CR121","unstructured":"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\u2013160 (2001) (in Russian)"},{"issue":"1","key":"12_CR122","doi-asserted-by":"crossref","first-page":"57","DOI":"10.3233\/FUN-2002-50104","volume":"50","author":"M.J. Moshkov","year":"2002","unstructured":"Moshkov, M.J.: On decision trees for (1,2)-Bayesian networks. Fundamenta Informaticae\u00a050(1), 57\u201376 (2002)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR123","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/3-540-45813-1_19","volume-title":"Rough Sets and Current Trends in Computing","author":"M.J. Moshkov","year":"2002","unstructured":"Moshkov, M.J.: On compressible information systems. In: Alpigini, J.J., Peters, J.F., Skowron, A., Zhong, N. (eds.) RSCTC 2002. LNCS (LNAI), vol.\u00a02475, pp. 156\u2013160. Springer, Heidelberg (2002)"},{"key":"12_CR124","unstructured":"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)"},{"key":"12_CR125","doi-asserted-by":"crossref","unstructured":"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.\u00a082(4) (2003), http:\/\/www.elsevier.nl\/locate\/entcs\/volume82.html","DOI":"10.1016\/S1571-0661(04)80716-3"},{"key":"12_CR126","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/3-540-39205-X_100","volume-title":"Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing","author":"M.J. Moshkov","year":"2003","unstructured":"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.\u00a02639, pp. 611\u2013614. Springer, Heidelberg (2003)"},{"issue":"4","key":"12_CR127","first-page":"345","volume":"54","author":"M.J. Moshkov","year":"2003","unstructured":"Moshkov, M.J.: Classification of infinite information systems depending on complexity of decision trees and decision rule systems. Fundamenta Informaticae\u00a054(4), 345\u2013368 (2003)","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"12_CR128","first-page":"51","volume":"55","author":"M.J. Moshkov","year":"2003","unstructured":"Moshkov, M.J.: Compressible infinite information systems. Fundamenta Informaticae\u00a055(1), 51\u201361 (2003)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR129","unstructured":"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.\u00a01, pp. 220\u2013222 (1996)"},{"key":"12_CR130","unstructured":"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\u2013141 (1996)"},{"issue":"2","key":"12_CR131","doi-asserted-by":"crossref","first-page":"145","DOI":"10.3233\/FI-1997-31204","volume":"31","author":"M.J. Moshkov","year":"1997","unstructured":"Moshkov, M.J., Chikalov, I.V.: Bounds on average weighted depth of decision trees. Fundamenta Informaticae\u00a031(2), 145\u2013156 (1997)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR132","unstructured":"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\u2013230 (1997)"},{"key":"12_CR133","unstructured":"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)"},{"issue":"3","key":"12_CR134","doi-asserted-by":"crossref","first-page":"295","DOI":"10.3233\/FI-2000-41302","volume":"41","author":"M.J. Moshkov","year":"2000","unstructured":"Moshkov, M.J., Chikalov, I.V.: On algorithm for constructing of decision trees with minimal depth. Fundamenta Informaticae\u00a041(3), 295\u2013299 (2000)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR135","unstructured":"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\u2013168 (2002) (in Russian)"},{"key":"12_CR136","unstructured":"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\u201356 (2002)"},{"key":"12_CR137","unstructured":"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\u20131647 (1997)"},{"key":"12_CR138","unstructured":"Moshkova, A.M.: Diagnosis of retaining faults of combinatorial circuits. Bulletin of Nizhny Novgorod State University. Mathematical Simulation and Optimal Control\u00a02, 204\u2013233 (1998) (in Russian)"},{"key":"12_CR139","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/3-540-69115-4_70","volume-title":"Rough Sets and Current Trends in Computing","author":"A.M. Moshkova","year":"1998","unstructured":"Moshkova, A.M.: On diagnosis of retaining faults in circuits. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS (LNAI), vol.\u00a01424, pp. 513\u2013516. Springer, Heidelberg (1998)"},{"key":"12_CR140","unstructured":"Moshkova, A.M.: On time complexity of \u201cretaining\u201d 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.\u00a01, pp. 372\u2013375 (2000)"},{"key":"12_CR141","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF02032305","volume":"52","author":"W. M\u00fcller","year":"1994","unstructured":"M\u00fcller, W., Wysotzki, F.: Automatic construction of decision trees for classification. Annals of Operations Research\u00a052, 231\u2013247 (1994)","journal-title":"Annals of Operations Research"},{"key":"12_CR142","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.63","volume":"2","author":"S.K. Murthy","year":"1994","unstructured":"Murthy, S.K., Kasif, S., Salzberg, S.: A system for induction of oblique decision trees. Journal of Artificial Intelligence Research\u00a02, 1\u201333 (1994)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1-2","key":"12_CR143","doi-asserted-by":"crossref","first-page":"145","DOI":"10.3233\/FI-1998-341205","volume":"34","author":"H.S. Nguyen","year":"1998","unstructured":"Nguyen, H.S.: From optimal hyperplanes to optimal decision trees. Fundamenta Informaticae\u00a034(1-2), 145\u2013174 (1998)","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"12_CR144","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3233\/FUN-2001-48105","volume":"48","author":"H.S. Nguyen","year":"2001","unstructured":"Nguyen, H.S.: On efficient handling of continuous attributes in large data bases. Fundamenta Informaticae\u00a048(1), 61\u201381 (2001)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR145","unstructured":"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\u2013482. Phisica- Verlag\/A Springer-Verlag Company, Heidelberg 1998)"},{"issue":"1-2","key":"12_CR146","doi-asserted-by":"crossref","first-page":"129","DOI":"10.3233\/FI-1998-341205","volume":"34","author":"S.H. Nguyen","year":"1998","unstructured":"Nguyen, S.H., Nguyen, H.S.: Pattern extraction from data. Fundamenta Informaticae\u00a034(1-2), 129\u2013144 (1998)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR147","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-540-48061-7_18","volume-title":"New Directions in Rough Sets, Data Mining, and Granular-Soft Computing","author":"H.S. Nguyen","year":"1999","unstructured":"Nguyen, H.S., Slezak, D.: Approximate reducts and association rules \u2013 correspondence and complexity results. In: Zhong, N., Skowron, A., Ohsuga, S. (eds.) RSFDGrC 1999. LNCS (LNAI), vol.\u00a01711, pp. 137\u2013145. Springer, Heidelberg (1999)"},{"key":"12_CR148","unstructured":"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.\u00a05, pp. 116\u2013126 (1969) (in Russian)"},{"key":"12_CR149","first-page":"61","volume-title":"Methods of Discrete Analysis","author":"E.A. Okolnishnikova","year":"1991","unstructured":"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.\u00a051, pp. 61\u201383. IM SO AN USSR Publishers, Novosibirsk (1991) (in Russian)"},{"key":"12_CR150","doi-asserted-by":"crossref","unstructured":"Pal, S.K., Polkowski, L., Skowron, A. (eds.): Rough-Neural Computing. Techniques for Computing with Words. Springer Verlag series in Cognitive Technologies, Berlin (2003)","DOI":"10.1007\/978-3-642-18859-6"},{"key":"12_CR151","unstructured":"Parchomenko, P.P.: Theory of questionnaires. Automation and Telemechanics\u00a04, 140\u2013159 (1970) (in Russian)"},{"key":"12_CR152","volume-title":"Fundamentals of Technical Diagnosis","author":"P.P. Parchomenko","year":"1981","unstructured":"Parchomenko, P.P., Sogomonyan, E.S.: Fundamentals of Technical Diagnosis. Energoizdat Publishers, Moscow (1981) (in Russian)"},{"key":"12_CR153","volume-title":"Information Systems \u2013 Theoretical Foundations","author":"Z. Pawlak","year":"1981","unstructured":"Pawlak, Z.: Information Systems \u2013 Theoretical Foundations. PWN, Warsaw (1981) (in Polish)"},{"key":"12_CR154","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01001956","volume":"11","author":"Z. Pawlak","year":"1982","unstructured":"Pawlak, Z.: Rough sets. International J. Comp. Inform. Science\u00a011, 341\u2013356 (1982)","journal-title":"International J. Comp. Inform. Science"},{"key":"12_CR155","unstructured":"Pawlak, Z.: Rough classification. Report of the Computing Center of the Polish Academy of Sciences\u00a0506 (1983)"},{"key":"12_CR156","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0165-0114(85)80029-4","volume":"17","author":"Z. Pawlak","year":"1985","unstructured":"Pawlak, Z.: Rough sets and fuzzy sets. Fuzzy Sets and Systems\u00a017, 99\u2013102 (1985)","journal-title":"Fuzzy Sets and Systems"},{"key":"12_CR157","series-title":"Lecture Notes in Computer Science","first-page":"186","volume-title":"Computation Theory","author":"Z. Pawlak","year":"1985","unstructured":"Pawlak, Z.: Rough sets and decision tables. In: Skowron, A. (ed.) SCT 1984. LNCS, vol.\u00a0208, pp. 186\u2013196. Springer, Heidelberg (1985)"},{"key":"12_CR158","first-page":"551","volume":"33","author":"Z. Pawlak","year":"1985","unstructured":"Pawlak, Z.: On rough dependency of attributes in information systems. Bull. Polish Acad. Sci. Tech.\u00a033, 551\u2013599 (1985)","journal-title":"Bull. Polish Acad. Sci. Tech."},{"key":"12_CR159","first-page":"553","volume":"34","author":"Z. Pawlak","year":"1986","unstructured":"Pawlak, Z.: On decision tables. Bull. Polish Acad. Sci. Tech.\u00a034, 553\u2013572 (1986)","journal-title":"Bull. Polish Acad. Sci. Tech."},{"key":"12_CR160","first-page":"253","volume":"35","author":"Z. Pawlak","year":"1987","unstructured":"Pawlak, Z.: Rough logic. Bull. Polish Acad. Sci. Tech.\u00a035, 253\u2013258 (1987)","journal-title":"Bull. Polish Acad. Sci. Tech."},{"key":"12_CR161","first-page":"85","volume":"33","author":"Z. Pawlak","year":"1987","unstructured":"Pawlak, Z.: Decision tables \u2013 a rough set approach. Bull. of EATCS\u00a033, 85\u201396 (1987)","journal-title":"Bull. of EATCS"},{"key":"12_CR162","volume-title":"Rough Sets \u2013 Theoretical Aspects of Reasoning about Data","author":"Z. Pawlak","year":"1991","unstructured":"Pawlak, Z.: Rough Sets \u2013 Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)"},{"key":"12_CR163","volume-title":"Probabilistic Inference in Intelligent Systems","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic Inference in Intelligent Systems. Morgan Kaufman, San Francisco (1988)"},{"issue":"1-2","key":"12_CR164","first-page":"157","volume":"51","author":"J.F. Peters","year":"2002","unstructured":"Peters, J.F., Skowron, A., Stepaniuk, J., Ramanna, S.: Towards an ontology of approximate reason. Fundamenta Informaticae\u00a051(1-2), 157\u2013173 (2002)","journal-title":"Fundamenta Informaticae"},{"key":"12_CR165","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/3-540-44967-1_44","volume-title":"Fuzzy Sets and Systems - IFSA 2003","author":"J.F. Peters","year":"2003","unstructured":"Peters, J.F., Skowron, A., Synak, P., Ramanna, S.: Rough sets and information granulation. In: De Baets, B., Kaynak, O., Bilgi\u00e7, T. (eds.) IFSA 2003. LNCS, vol.\u00a02715, pp. 370\u2013377. Springer, Heidelberg (2003)"},{"key":"12_CR166","volume-title":"Theorie des Questionnaires","author":"C.F. Picard","year":"1965","unstructured":"Picard, C.F.: Theorie des Questionnaires. Gauthier-Villars, Paris (1965)"},{"key":"12_CR167","unstructured":"Picard, C.F.: Graphes et Questionnaires, vol.\u00a01, 2. Gauthier-Villars, Paris (1972)"},{"key":"12_CR168","series-title":"Mathematical Foundations (Advances in Soft Computing)","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-7908-1776-8","volume-title":"Rough Sets","author":"L. Polkowski","year":"2002","unstructured":"Polkowski, L.: Rough Sets. Mathematical Foundations (Advances in Soft Computing). Physica-Verlag, Heidelberg (2002)"},{"key":"12_CR169","doi-asserted-by":"crossref","unstructured":"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.\u00a056. Phisica-Verlag\/A Springer-Verlag Company, Heidelberg 2000)","DOI":"10.1007\/978-3-7908-1840-6"},{"key":"12_CR170","volume-title":"Decision Tables: Theory and Practice","author":"S.L. Pollack","year":"1971","unstructured":"Pollack, S.L.: Decision Tables: Theory and Practice. J. Wiley & Sons Inc., Chichester (1971)"},{"key":"12_CR171","doi-asserted-by":"publisher","first-page":"163","DOI":"10.2307\/2370324","volume":"43","author":"E. Post","year":"1921","unstructured":"Post, E.: Introduction to a general theory of elementary propositions. Amer. J. Math.\u00a043, 163\u2013185 (1921)","journal-title":"Amer. J. Math."},{"key":"12_CR172","volume-title":"Annals of Math. Studies","author":"E. Post","year":"1941","unstructured":"Post, E.: Two-valued iterative systems of mathematical logic. In: Annals of Math. Studies, vol.\u00a05. Princeton Univ. Press, Princeton (1941)"},{"key":"12_CR173","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1985)"},{"key":"12_CR174","unstructured":"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)"},{"issue":"1","key":"12_CR175","first-page":"81","volume":"1","author":"J.R. Quinlan","year":"1986","unstructured":"Quinlan, J.R.: Induction of decision trees. Machine Learning\u00a01(1), 81\u2013106 (1986)","journal-title":"Machine Learning"},{"key":"12_CR176","unstructured":"Quinlan, J.R.: Generating production rules from decision trees. In: Proc. of the Tenth Int. Joint Conf. on AI, pp. 304\u2013307 (1987)"},{"key":"12_CR177","volume-title":"C4.5: Programs for Machine Learning","author":"J.R. Quinlan","year":"1993","unstructured":"Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo (1993)"},{"key":"12_CR178","volume-title":"Reliability and Diagnosis of Circuits","author":"N.P. Redkin","year":"1992","unstructured":"Redkin, N.P.: Reliability and Diagnosis of Circuits. Moscow University Publishers, Moscow (1992) (in Russian)"},{"key":"12_CR179","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1016\/0005-1098(78)90005-5","volume":"14","author":"J. Rissanen","year":"1978","unstructured":"Rissanen, J.: Modeling by shortest data description. Automatica\u00a014, 465\u2013471 (1978)","journal-title":"Automatica"},{"key":"12_CR180","doi-asserted-by":"crossref","unstructured":"Roth, J.P.: Diagnosis of automata failures: a calculus and method. Journal Research and Development, 278\u2013291 (1966)","DOI":"10.1147\/rd.104.0278"},{"key":"12_CR181","unstructured":"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.\u00a0103 (1969)"},{"key":"12_CR182","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. of Combinatorial Theory (A)\u00a013, 145\u2013147 (1972)","journal-title":"J. of Combinatorial Theory (A)"},{"key":"12_CR183","doi-asserted-by":"crossref","first-page":"241","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S. Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. of Mathematics\u00a041, 241\u2013261 (1972)","journal-title":"Pacific J. of Mathematics"},{"key":"12_CR184","first-page":"86","volume-title":"Combinatorial-Algebraic and Probabilistic Methods in Applied Mathematics","author":"V.I. Shevtchenko","year":"1988","unstructured":"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\u201397. Gorky University Publishers, Gorky (1988) (in Russian)"},{"key":"12_CR185","first-page":"129","volume-title":"Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis","author":"V.I. Shevtchenko","year":"1989","unstructured":"Shevtchenko, V.I.: On complexity of diagnosis of faults of the type \u201c\u2295\u201d in combinatorial circuits. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods of Discrete Analysis, pp. 129\u2013140. Gorky University Publishers, Gorky (1989) (in Russian)"},{"key":"12_CR186","first-page":"125","volume-title":"Combinatorial-Algebraic and Probabilistic Methods and its Application","author":"V.I. Shevtchenko","year":"1990","unstructured":"Shevtchenko, V.I.: On complexity of diagnosis of faults of types \u201c0\u201d, \u201c1\u201d, \u201c&\u201d and \u201c\u2228\u201d in combinatorial circuits. In: Markov, A.A. (ed.) Combinatorial-Algebraic and Probabilistic Methods and its Application, pp. 125\u2013150. Gorky University Publishers, Gorky (1990)"},{"key":"12_CR187","first-page":"63","volume":"1","author":"V.I. Shevtchenko","year":"1994","unstructured":"Shevtchenko, V.I.: On depth of conditional tests for diagnosis of \u201cnegation\u201d type faults in circuits. Siberian Journal on Operations Research\u00a01, 63\u201374 (1994) (in Russian)","journal-title":"Siberian Journal on Operations Research"},{"key":"12_CR188","unstructured":"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\u2013203. The Society for Computer Simulation, San Diego (1995)"},{"key":"12_CR189","unstructured":"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\u2013330 (1996)"},{"issue":"1\u20134","key":"12_CR190","first-page":"247","volume":"1","author":"V.I. Shevtchenko","year":"1996","unstructured":"Shevtchenko, V.I.: On complexity of conditional tests for diagnosis of circuits. Intellectual Systems\u00a01(1\u20134), 247\u2013251 (1996) (in Russian)","journal-title":"Intellectual Systems"},{"key":"12_CR191","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/3-540-69115-4_71","volume-title":"Rough Sets and Current Trends in Computing","author":"V.I. Shevtchenko","year":"1998","unstructured":"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.\u00a01424, pp. 517\u2013520. Springer, Heidelberg (1998)"},{"key":"12_CR192","unstructured":"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\u2013238 (2001) (in Russian)"},{"key":"12_CR193","unstructured":"Skowron, A.: Rough sets in KDD. In: Proceedings of the 16-th World Computer Congress (IFIP 2000), Beijing, China, pp. 1\u201314 (2000)"},{"issue":"6","key":"12_CR194","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/S0167-8655(02)00195-2","volume":"24","author":"A. Skowron","year":"2003","unstructured":"Skowron, A., Pal, S.K. (eds.): Special issue Rough sets, pattern recognition and data mining. Pattern Recognition Letters\u00a024(6), 829\u2013933 (2003)","journal-title":"Pattern Recognition Letters"},{"key":"12_CR195","first-page":"134","volume-title":"Handbook of KDD","author":"A. Skowron","year":"2002","unstructured":"Skowron, A., Pawlak, Z., Komorowski, J., Polkowski, L.: A rough set perspective on data and knowledge. In: Kloesgen, W., \u017bytkow, J. (eds.) Handbook of KDD, pp. 134\u2013149. Oxford University Press, Oxford (2002)"},{"key":"12_CR196","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-1-4613-1461-5_14","volume-title":"Rough Sets and Data Mining: Analysis for Imprecise Data","author":"A. Skowron","year":"1997","unstructured":"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\u2013300. Kluwer Academic Publishers, Boston (1997)"},{"key":"12_CR197","series-title":"Handbook of Applications and Advances of the Rough Set Theory","doi-asserted-by":"crossref","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. Handbook of Applications and Advances of the Rough Set Theory, pp. 331\u2013362. Kluwer Academic Publishers, Dordrecht (1992)"},{"key":"12_CR198","doi-asserted-by":"crossref","unstructured":"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\u2013636 (2003)","DOI":"10.1007\/978-3-642-18859-6_25"},{"key":"12_CR199","unstructured":"Slezak, D.: Approximate decision reducts. Ph.D. thesis. Warsaw University (2002) (in Polish)"},{"key":"12_CR200","doi-asserted-by":"crossref","unstructured":"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.\u00a0125, pp. 109\u2013121. Phisica- Verlag, A Springer-Verlag Company, Heidelberg (2003)","DOI":"10.1007\/978-3-540-36473-3_11"},{"key":"12_CR201","series-title":"Handbook of Applications and Advances of the Rough Set Theory","volume-title":"Intelligent Decision Support","year":"1992","unstructured":"Slowinski, R. (ed.): Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory. Kluwer Academic Publishers, Dordrecht (1992)"},{"key":"12_CR202","first-page":"91","volume-title":"Discrete Analysis","author":"N.A. Soloviev","year":"1968","unstructured":"Soloviev, N.A.: On certain property of tables with uncancellable tests of equal length. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol.\u00a012, pp. 91\u201395. Nauka Publishers, Novosibirsk (1968) (in Russian)"},{"key":"12_CR203","volume-title":"Tests (Theory, Construction, Applications)","author":"N.A. Soloviev","year":"1978","unstructured":"Soloviev, N.A.: Tests (Theory, Construction, Applications). Nauka Publishers, Novosibirsk (1978) (in Russian)"},{"key":"12_CR204","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J.M. Steele","year":"1982","unstructured":"Steele, J.M., Yao, A.C.: Lower bounds for algebraic decision trees. J. of Algorithms\u00a03, 1\u20138 (1982)","journal-title":"J. of Algorithms"},{"key":"12_CR205","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/S0167-8655(02)00196-4","volume":"24","author":"R. Swiniarski","year":"2003","unstructured":"Swiniarski, R., Skowron, A.: Rough set methods in feature selection and recognition. Pattern Recognition Letters\u00a024, 833\u2013849 (2003)","journal-title":"Pattern Recognition Letters"},{"key":"12_CR206","volume-title":"Opponent Strategy Method in Optimal Search Problems","author":"V.P. Tarasova","year":"1988","unstructured":"Tarasova, V.P.: Opponent Strategy Method in Optimal Search Problems. Moscow University Publishers, Moscow (1988) (in Russian)"},{"key":"12_CR207","first-page":"63","volume":"55","author":"A. Tarski","year":"1949","unstructured":"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.\u00a055, 63\u201364 (1949)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"3","key":"12_CR208","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01145476","volume":"31","author":"V.A. Ufnarovskii","year":"1982","unstructured":"Ufnarovskii, V.A.: Criterion of growth of graphs and algebras defined by words. Mathematical Notes\u00a031(3), 465\u2013472 (1982) (in Russian)","journal-title":"Mathematical Notes"},{"issue":"4","key":"12_CR209","first-page":"603","volume":"42","author":"A.B. Ugolnikov","year":"1987","unstructured":"Ugolnikov, A.B.: On depth and polynomial equivalence of formulas for closed classes of binary logic. Mathematical Notes\u00a042(4), 603\u2013612 (1987) (in Russian)","journal-title":"Mathematical Notes"},{"issue":"2","key":"12_CR210","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications\u00a016(2), 264\u2013280 (1971)","journal-title":"Theory of Probability and its Applications"},{"key":"12_CR211","first-page":"98","volume":"4","author":"M.P. Vasilevsky","year":"1973","unstructured":"Vasilevsky, M.P.: On recognition of faults of automata. Cybernetics\u00a04, 98\u2013108 (1973) (in Russian)","journal-title":"Cybernetics"},{"key":"12_CR212","first-page":"19","volume":"2","author":"M.P. Vasilevsky","year":"1974","unstructured":"Vasilevsky, M.P.: On deciphering of automata. Cybernetics\u00a02, 19\u201323 (1974) (in Russian)","journal-title":"Cybernetics"},{"key":"12_CR213","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. John Wiley and Sons\/B.G. Teubner, Stuttgart (1987)"},{"key":"12_CR214","unstructured":"Yablonskii, S.V.: Tests. Encyklopaedia Kybernetiki. In: Glushkov, V.M. (ed.) Main Editorial Staff of Ukrainian Soviet Encyklopaedia, Kiev, pp. 431\u2013432 (1975) (in Russian)"},{"key":"12_CR215","first-page":"5","volume-title":"Mathematical Problems of Cybernetics","author":"S.V. Yablonskii","year":"1988","unstructured":"Yablonskii, S.V.: Some problems of reliability and diagnosis in control systems. In: Yablonskii, S.V. (ed.) Mathematical Problems of Cybernetics, vol.\u00a01, pp. 5\u201325. Nauka Publishers, Moscow (1988) (in Russian)"},{"issue":"4","key":"12_CR216","first-page":"182","volume":"10","author":"S.V. Yablonskii","year":"1955","unstructured":"Yablonskii, S.V., Chegis, I.A.: On tests for electric circuits. UMN\u00a010(4), 182\u2013184 (1955) (in Russian)","journal-title":"UMN"},{"key":"12_CR217","volume-title":"Functions of Algebra of Logic and Classes of Post","author":"S.V. Yablonskii","year":"1966","unstructured":"Yablonskii, S.V., Gavrilov, G.P., Kudriavtzev, V.B.: Functions of Algebra of Logic and Classes of Post. Nauka Publishers, Moscow (1966) (in Russian)"},{"key":"12_CR218","doi-asserted-by":"crossref","unstructured":"Yao, A.: Algebraic decision trees and Euler characteristics. In: Proceedings IEEE FOCS, pp. 268\u2013277 (1992)","DOI":"10.1109\/SFCS.1992.267765"},{"key":"12_CR219","doi-asserted-by":"crossref","unstructured":"Yao, A.: Decision tree complexity and Betti numbers. In: Proceedings ACM STOC, pp. 615\u2013624 (1994)","DOI":"10.1145\/195058.195414"},{"key":"12_CR220","first-page":"23","volume-title":"Discrete Analysis","author":"J.I. Zhuravlev","year":"1964","unstructured":"Zhuravlev, J.I.: On a class of partial Boolean functions. In: Zhuravlev, J.I. (ed.) Discrete Analysis, vol.\u00a02, pp. 23\u201327. IM SO AN USSR Publishers, Novosibirsk (1964) (in Russian)"}],"container-title":["Lecture Notes in Computer Science","Transactions on Rough Sets III"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11427834_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T11:00:08Z","timestamp":1740222008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11427834_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540259985","9783540318507"],"references-count":220,"URL":"https:\/\/doi.org\/10.1007\/11427834_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}