A further study on simplification of decision tables

In traditional rough set theory, the simplification of a decision table was investigated and minimal algorithms were introduced to express its result. However, the optimization of minimal algorithms is still left aside. In this paper, we first propose an algorithm for computing all reducts of every decision rule in a decision table, and then we explore three optimal problems of minimal algorithms of a decision table. Specifically, we prove them to be NP-hard and give heuristic algorithms for solving them. Finally, these heuristic algorithms are programmed and demonstrated on three examples.