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

Janos, Demetrovics; Thi, Vu Duc; Giang, Nguyen Long; Duong, Tran Huy

Serdica Journal of Computing (2015)

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

## Access Full Article

top## Abstract

top## How to cite

topJanos, 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 ?

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