BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2015 >
Volume 9 Number 2 >

Please use this identifier to cite or link to this item:

Title: On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables
Authors: Janos, Demetrovics
Thi, Vu Duc
Giang, Nguyen Long
Duong, Tran Huy
Keywords: Decision Table
Relation Schema
Minimal Set
Time Complexity
Issue Date: 2015
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 9, No 2, (2015), 167p-176p
Abstract: In recent years, rough set approach computing issues concerning reducts of decision tables have attracted the attention of many researchers. In this paper, we present the time complexity of an algorithm computing reducts of decision tables by relational database approach. Let DS = (U, C ∪ {d}) be a consistent decision table, we say that A ⊆ C is a relative reduct of DS if A contains a reduct of DS. Let s = <C ∪ {d} , F> be a relation schema on the attribute set C ∪ {d}, we say that A ⊆ C is a relative minimal set of the attribute d if A contains a minimal set of d. Let Qd be the family of all relative reducts of DS, and Pd be the family of all relative minimal sets of the attribute d on s. We prove that the problem whether Qd ⊆ Pd is co-NP-complete. However, the problem whether Pd ⊆ Qd is in P .
ISSN: 1312-6555
Appears in Collections:Volume 9 Number 2

Files in This Item:

File Description SizeFormat
sjc-vol9-num2-2015-p167-p176.pdf121.14 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License