Some NP-complete problems for attribute reduction in consistent decision tables

DOI10.55630/SJC.2020.14.27-41MaRDI QIDQ5868044zbMATH OpenOpenAlexFDO

Authors Phan Dang Khoa, Vu Duc Thi, Pham Viet Anh, J. Demetrovics

Publication date 19 September 2022

Published in Serdica Journal of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.55630/sjc.2020.14.27-41

zbMATH Keywords

computational complexityNP-completenessrough set theoryattribute reductionconsistent decision table

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reasoning under uncertainty in the context of artificial intelligence (68T37) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30)

Recommendations

• On the time complexity of the problem related to reducts of consistent decision tables
• Searching for Reductive Attributes in Decision Tables
• scientific article; zbMATH DE number 23766
• The M-Relative Reduct Problem
• An efficient method to reduce the size of consistent decision tables

Cites work

• scientific article; zbMATH DE number 6622730 (Why is no real title available?)
• scientific article; zbMATH DE number 53312 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 846961 (Why is no real title available?)
• A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets
• Attribute reduction based on consistent covering rough set and its application
• Reduction of the decision table: A rough approach
• Rough Set Attribute Reduction in Decision Systems
• Rudiments of rough sets

Cited in

(6)

• The problem of finding the simplest classifier ensemble is NP-hard -- a rough-set-inspired formulation based on decision bireducts
• The relationship between the unicost set covering problem and the attribute reduction problem in rough set theory
• An efficient method to reduce the size of consistent decision tables
• On the complexity of redescription mining
• Rough Sets and Current Trends in Computing
• On the time complexity of the problem related to reducts of consistent decision tables

This page was built for publication: Some NP-complete problems for attribute reduction in consistent decision tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868044)