On Construction of Partial Reducts and Irreducible Partial Decision Rules

Issue title: New Frontiers in Scientific Discovery – Commemorating the Life and Work of Zdzislaw Pawlak

Article type: Research Article

Authors: Moshkov, Mikhail Ju. | Piliszczuk, Marcin | Zielosko, Beata

Affiliations: Institute of Computer Science, University of Silesia, 39, B�dzińska St., Sosnowiec, 41-200, Poland. E-mail: [email protected] | ING Bank Śl�ski S.A., 34, Sokolska St., Katowice, 40-086, Poland. E-mail: [email protected] | Institute of Computer Science, University of Silesia, 39, B�dzińska St., Sosnowiec, 41-200, Poland. E-mail: [email protected]

Abstract: In the paper for the most part of binary decision tables upper and lower bounds on the cardinality of partial reducts and length of irreducible partial decision rules are obtained. The number of partial reducts and the number of irreducible partial decision rules are evaluated. Complexity of algorithms for construction of all partial reducts and all irreducible partial decision rules is studied on the basis of obtained bounds.

Keywords: partial reducts, irreducible partial decision rules, algorithms for construction, complexity

Journal: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 357-374, 2007