A Complete Reduction Algorithm Based on Simple Discernibility Matrix
Wei Song · Computer Engineering and Applications Journal · 2006
Because the definition of attribution reduction based on old discernibility matrix is not the same as the definition of attribution reduction based on positive region,a simple discernibility matrix and the corresponding definition of attribution reduction are provided.At the same time,it is proved that the above definition of attribution reduction is the same as the definition of attribution reduction based on positive region.For first computing IND(C) in the simple discernibility matrix,a good algorithm for computing IND(C) is designed,it's time complexity is cut down to O(|C‖U|).On this condition,a complete attribution reduction algorithm is designed,time complexity and space complexity of the new algorithm are cut down to max{O(|C|2(|U′pos‖U/C|)),O(|C‖U|)}and max{O(|U|),O(|C|(|U′pos‖U/C|))} respectively.