Tree Expressions for Information Systems

The discernibility matrix is one of the most important approaches tocomputing positive region, reduct, core and value reduct in rough sets.The subject of this paper is to develop a parallel approach of it,called tree expression. Its computational complexity forpositive region and reduct is O(m^2\tm n) instead of O(m\tm n^2) indiscernibility-matrix-based approach, and is not over O(n^2) forother concepts in rough sets, where m and n are the numbers ofattributes and objects respectively in a given dataset (also called an``\it information system'' in rough sets). This approach suitsinformation systems with n\gg m and containing over one million objects.