Second Attribute Algorithm Based on Tree Expression

One view of finding a personalized solution of reduct in an informationsystem is grounded on the viewpoint that attribute order can serve as akind of semantic representation of user requirements. Thus the problemof finding personalized solutions can be transformed into computing thereduct on an attribute order. The second attribute theorem describes therelationship between the set of attribute orders and the set of reducts,and can be used to transform the problem of searching solutions to meetuser requirements into the problem of modifying reduct based on a givenattribute order. An algorithm is implied based on the second attributetheorem, with computation on the discernibility matrix. Its timecomplexity is O(n^2*m) (n is the number of the objects andm the number of the attributes of an information system). Thispaper presents another effective second attribute algorithm forfacilitating the use of the second attribute theorem, with computationon the tree expression of an information system. The time complexity ofthe new algorithm is linear in n. This algorithm is proved to beequivalent to the algorithm on the discernibility matrix.