<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The problem of finding reducts plays an important role in processing information on decision tables. The objective of the attribute reduction problem is to reject a redundant attribute in order to find a core attribute for data processing. The attribute reduction in decision tables is the process of finding a minimal subset of conditional attributes which preserve the classification ability of decision tables. In this paper we present the time complexity of the problem of finding all reducts of a consistent decision table. We prove that this time complexity is exponential with respect to the number of attributes of the decision tables. Our proof is performed in two steps. The first step is to show that there exists an exponential algorithm which finds all reducts. The other step is to prove that the time complexity of the problem of finding all reducts of a decision table is not less than exponential.</p></abstract>

The problem of finding reducts plays an important role in processing information on decision tables. The objective of the attribute reduction problem is to reject a redundant attribute in order to find a core attribute for data processing. The attribute reduction in decision tables is the process of finding a minimal subset of conditional attributes which preserve the classification ability of decision tables. In this paper we present the time complexity of the problem of finding all reducts of a consistent decision table. We prove that this time complexity is exponential with respect to the number of attributes of the decision tables. Our proof is performed in two steps. The first step is to show that there exists an exponential algorithm which finds all reducts. The other step is to prove that the time complexity of the problem of finding all reducts of a decision table is not less than exponential.

On Finding All Reducts of Consistent Decision Tables

Institute for Computer and Control (SZTAKI), Hungarian Academy of Sciences

Institute of Information Technology, VNU, Viet Nam

Institute of Information Technology, VAST, Viet Nam

Cybernetics and Information Technologies

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"On Finding All Reducts of Consistent Decision Tables"}

The problem of finding reducts plays an important role in processing information on decision tables. The objective of the attribute reduction problem is to...

On Finding All Reducts of Consistent Decision Tables

Published Online: Jan 31, 2015

Page range: 3 - 10

DOI: https://doi.org/10.1515/cait-2014-0001

© 2014 Demetrovics Janos et. al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.