An Efficient Algorithm for Determining the Set of All Reductive Attributes in Incomplete Decision Tables

Abstract

In rough set theory, the number of all reducts for a given decision table can be exponential with respect to the number of attributes. This paper investigates the problem of determining the set of all reductive attributes which are present in at least one reduct of an incomplete decision table. We theoretically prove that this problem can be solved in polynomial time. This result shows that the problem of determining the union of all reducts can be solved in polynomial time, and the problem of determining the set of all redundant attributes which are not present in any reducts can also be solved in polynomial time.

Keywords

• rough sets
• reducts
• incomplete decision tables
• tolerance matrix
• tolerance function