Reduct and Attribute Order

Based on the principle of discernibility matrix, a kind of reductionalgorithm with attribute order has been developed and its solution hasbeen proved to becomplete for reduct and unique for a given attribute order. Being calledthe reduct problem, this algorithm can be regarded as a mappingR=Reduct(S) from the attribute order space Theta to the reduct space R for an information system, where U is the universe and C and D aretwo sets of condition and decision attributesrespectively. This paper focuses on the reverse problem of reductproblem S=Order?, I.e., for a given reduct R of aninformation system, we determine the solution of S=Order? inthe space Theta. First, we need to prove thatthere is at least one attribute order S such thatS=Order?. Then, some decision rules are proposed,which can be used directly to decide whether the pair of attributeorders has the same reduct. The main method is based on the factthat an attribute order can be transformed into another one by movingthe attribute for limited times. Thus, the decision of the pair ofattribute orders can be altered to the decision of the sequence ofneighboring pairs of attribute orders. Therefore,the basic theorem of neighboring pair of attribute orders is firstproved, then, the decision theorem of attribute order is provedaccordingly by the second attribute.