Affiliations: Division of Mathematical and Computer Sciences and
Engineering, King Abdullah University of Science and Technology, P.O. Box 55455,
Jeddah 21534, Saudi Arabia. mikhail.moshkov@kaust.edu.sa | Institute of Mathematics, Warsaw University, Banacha 2,
02-097 Warsaw, Poland. skowron@mimuw.edu.pl | Chair of Computer Science, University of
Rzeszów Dekerta 2, 35-030 Rzeszów, Poland.
zsuraj@univ.rzeszow.pl
Note: [] Address for correspondence: Institute of Mathematics, Warsaw
University, Banacha 2, 02-097 Warsaw, Poland
Abstract: The minimal inhibitory rules for information systems can be used for
construction of classifiers. We show that almost all information systems from a
certain large class of information systems have relatively short minimal
inhibitory rules. However, the number of such rules is not polynomial in the
number of attributes and the number of objects. This class consists of all
k-valued information systems, k ⩾ 2, with the number of objects
polynomial in the number of attributes. Hence, for efficient construction of
classifiers some filtration techniques in rule generation are necessary.
Another way is to work with lazy classification algorithms based on inhibitory
rules.
Keywords: Information systems, minimal inhibitory rules, irreducible inconsistent systems of equations
