%0 Journal Article
%T Tree Expressions for Information Systems
%A Min Zhao
%A Su-Qing nan
%A Jue Wang
%A <br>Min Zhao
%A Su-Qing Han
%A and Jue Wang
%J 计算机科学技术学报
%D 2007
%I 
%X The discernibility matrix is one of the most important approaches to computing 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 for positive region and reduct is O(m 2 × n) instead of O(m × n 2) in discernibility-matrix-based approach, and is not over O(n 2) for other concepts in rough sets, where m and n are the numbers of attributes and objects respectively in a given dataset (also called an “information system” in rough sets). This approach suits information systems with n   m and containing over one million objects. Electronic supplementary material Electronic supplementary material is available for this article at and accessible for authorised users. This work is partially supported by the National Grand Fundamental Research 973 Program of China under Grant No. 2004CB318103 and the National Nature Science Foundation of China under Grant No. 60573078.
%K algorithms
%K tree expression
%K reduct theory<br>信息系统
%K 信息树
%K 粗集理论
%K 识别能力矩阵
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=9E39E51210A4AAEEA4E5A03FB60EED3E&yid=A732AF04DDA03BB3&vid=BC12EA701C895178&iid=0B39A22176CE99FB&sid=E42CAFB11D4BE21A&eid=F416A9924F23B020&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=1&reference_num=12