Some algorithms related to consistent decision table

Quang Minh Hoang, Vu Duc Thi, Nguyen Ngoc San


Rough set theory is useful mathematical tool developed to deal with vagueness and uncertainty. As an important concept of rough set theory, an attribute reduct is a subset of attributes that are jointly sufficient and individually necessary for preserving a particular property of the given information table. Rough set theory is also the most popular for generating decision rules from decision table. In this paper, we propose an algorithm finding object reduct of consistent decsion table. On the other hand, we also show an algorithm to find some attribute reducts and the correctness of our algorithms is proof-theoretically. These our algorithms have polynomial time complexity. Our finding object reduct helps other algorithms of finding attribute reducts become more effectively, especially as working with huge consistent decision table.


object reduct; attribute reduct; rough set theory; decision table; decision rules

Full Text:



Demetrovics, J. and Thi, V. D. Keys, antikeys and prime attributes. In Annales Univ. Sci. Budapest, Sect. Comp, volume 8, pages 35--52 (1987)

Demetrovics, J. and Thi, V. D. Algorithms for generating an armstrong relation and inferring functional dependencies in the relational datamodel. Computers & Mathematics with Applications, 26(4), 43--55 (1993)

Pawlak, Z. Rough sets. International Journal of Computer & Information Sciences, 11(5), 341--356 (1982)

Pawlak, Z., Grzymala-Busse, J., Slowinski, R., and Ziarko, W. (1995). Rough sets. Communications of the ACM, 38(11), 88--95.

Skowron, A. and Rauszer, C. The discernibility matrices and functions in information systems. In Intelligent Decision Support, pages 331--362. Springer (1992)

Thi, V. D. The minimal keys and antikeys. Acta Cybernetica, 7(4), 361--371 (1986)

Thi, V. D. and Giang, N. L. A method to construct decision table from relation scheme. Cybernetics and Information Technologies, 11(3), 32--41 (2011)


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology