The depth of decision trees for binary problems

M. Yu Moshkov

doi:10.3103/S0027132207030059

The depth of decision trees for binary problems

Research output: Contribution to journal › Article › peer-review

Abstract

The depth of decision trees for binary problems (problems with decisions 0 or 1) over check systems from some class is studied in this paper. It is shown that if the number of checkings in the problem description increases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or increases almost as a logarithmic function, or increases like a linear function.

Original language	English (US)
Pages (from-to)	108-111
Number of pages	4
Journal	Moscow University Mathematics Bulletin
Volume	62
Issue number	3
DOIs	https://doi.org/10.3103/S0027132207030059
State	Published - Jun 2007
Externally published	Yes

ASJC Scopus subject areas

General Mathematics

Access to Document

10.3103/S0027132207030059

Cite this

@article{8d1e1df68d814057a42a2197e7da293c,

title = "The depth of decision trees for binary problems",

abstract = "The depth of decision trees for binary problems (problems with decisions 0 or 1) over check systems from some class is studied in this paper. It is shown that if the number of checkings in the problem description increases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or increases almost as a logarithmic function, or increases like a linear function.",

author = "Moshkov, {M. Yu}",

year = "2007",

month = jun,

doi = "10.3103/S0027132207030059",

language = "English (US)",

volume = "62",

pages = "108--111",

journal = "Moscow University Mathematics Bulletin",

issn = "0027-1322",

publisher = "Allerton Press Inc.",

number = "3",

}

TY - JOUR

T1 - The depth of decision trees for binary problems

AU - Moshkov, M. Yu

PY - 2007/6

Y1 - 2007/6

N2 - The depth of decision trees for binary problems (problems with decisions 0 or 1) over check systems from some class is studied in this paper. It is shown that if the number of checkings in the problem description increases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or increases almost as a logarithmic function, or increases like a linear function.

AB - The depth of decision trees for binary problems (problems with decisions 0 or 1) over check systems from some class is studied in this paper. It is shown that if the number of checkings in the problem description increases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or increases almost as a logarithmic function, or increases like a linear function.

UR - http://www.scopus.com/inward/record.url?scp=84859582228&partnerID=8YFLogxK

U2 - 10.3103/S0027132207030059

DO - 10.3103/S0027132207030059

M3 - Article

AN - SCOPUS:84859582228

SN - 0027-1322

VL - 62

SP - 108

EP - 111

JO - Moscow University Mathematics Bulletin

JF - Moscow University Mathematics Bulletin

IS - 3

ER -

The depth of decision trees for binary problems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this