Decision trees based on 1-consequences

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued non-constant functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should determine values of these attributes. As algorithms for problem solving, we study decision trees that use arbitrary attributes from the considered infinite set of attributes and solve the problem based on 1-consequences. In such a tree, we take into account consequences each of which follows from one equation of the kind “attribute value” obtained during the decision tree work and ignore consequences that can be derived only from at least two equations. As time complexity, we study the depth of decision trees. We prove that in the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees based on 1-consequences grows either as a logarithm or linearly.
Original languageEnglish (US)
Pages (from-to)208-214
Number of pages7
JournalDiscrete Applied Mathematics
Volume302
DOIs
StatePublished - Jul 20 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Decision trees based on 1-consequences'. Together they form a unique fingerprint.

Cite this