Partial covers and inhibitory decision rules

Pawel Delimata, Mikhail Ju Moshkov, Andrzej Skowron, Zbigniew Suraj

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In this chapter, we consider algorithms for construction of partial inhibitory decision rules and some bounds on the length such rules. These investigations are based on the use of known results for partial covers. We show that: • Under some natural assumptions on the class NP, the greedy algorithm is close to the best polynomial approximate algorithms for the minimization of the length of partial inhibitory decision rules. • Based on an information received during the greedy algorithm work, it is possible to obtain nontrivial lower and upper bounds on the minimal length of partial inhibitory decision rules. • For the most part of randomly generated binary decision tables, greedy algorithm constructs simple partial inhibitory decision rules with relatively high accuracy. In particular, some theoretical results confirm the following 0.5-hypothesis for inhibitory decision rules: for the most part of decision tables for each row during each step the greedy algorithm chooses an attribute that separates from the considered row at least one-half of rows that should be separated. Similar results can be obtained for partial inhibitory association rules over information systems. To this end, it is enough to fix an arbitrary attribute a i of the information system as the decision attribute and study inhibitory association rules with the right-hand side of the kind ai ≠ c as inhibitory decision rules over the obtained decision system (decision table). © 2009 Springer-Verlag Berlin Heidelberg.
Original languageEnglish (US)
Pages (from-to)43-62
Number of pages20
JournalStudies in Computational Intelligence
StatePublished - Jan 1 2009
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-21

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Partial covers and inhibitory decision rules'. Together they form a unique fingerprint.

Cite this