<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

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

Institute of Computer and Automation, Hungarian Academy of Sciences

Institute of Information Technology, Vietnam Academy of Science and Technology (VAST). 18 Hoang Quoc Viet Road, Ha Noi, Viet Nam

Cybernetics and Information Technologies

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...

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

Online veröffentlicht: 31. Dez. 2013

Seitenbereich: 118 - 126

DOI: https://doi.org/10.2478/cait-2013-0058

This content is open access.