# On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables

• Volume: 9, Issue: 2, page 167-176
• ISSN: 1312-6555

top

## Abstract

top
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 .

## How to cite

top

Janos, Demetrovics, et al. "On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables." Serdica Journal of Computing 9.2 (2015): 167-176. <http://eudml.org/doc/281471>.

@article{Janos2015,
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 .},
author = {Janos, Demetrovics, Thi, Vu Duc, Giang, Nguyen Long, Duong, Tran Huy},
journal = {Serdica Journal of Computing},
keywords = {Decision Table; Reduct; Relation; Relation Schema; Minimal Set; Time Complexity},
language = {eng},
number = {2},
pages = {167-176},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables},
url = {http://eudml.org/doc/281471},
volume = {9},
year = {2015},
}

TY - JOUR
AU - Janos, Demetrovics
AU - Thi, Vu Duc
AU - Giang, Nguyen Long
AU - Duong, Tran Huy
TI - On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables
JO - Serdica Journal of Computing
PY - 2015
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 9
IS - 2
SP - 167
EP - 176
AB - 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 .
LA - eng
KW - Decision Table; Reduct; Relation; Relation Schema; Minimal Set; Time Complexity
UR - http://eudml.org/doc/281471
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.