On the class of restricted linear information systems

Mikhail Ju Moshkov

doi:10.1016/j.disc.2007.03.002

On the class of restricted linear information systems

Mikhail Ju Moshkov^*

^*Corresponding author for this work

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

11 Scopus citations

Abstract

In the paper the class of restricted linear information systems is described completely. For decision tables over each such information system there exist low upper bounds on minimal complexity of decision trees and polynomial algorithms of decision tree optimization for various complexity measures. A corollary connected with combinatorial geometry is considered.

Original language	English (US)
Pages (from-to)	2837-2844
Number of pages	8
Journal	Discrete Mathematics
Volume	307
Issue number	22
DOIs	https://doi.org/10.1016/j.disc.2007.03.002
State	Published - Oct 28 2007
Externally published	Yes

Keywords

Complexity
Decision tree
Information system
Optimization

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.03.002

Cite this

@article{cdd6ca9c4fc74974be0bf332f2cb68e7,

title = "On the class of restricted linear information systems",

abstract = "In the paper the class of restricted linear information systems is described completely. For decision tables over each such information system there exist low upper bounds on minimal complexity of decision trees and polynomial algorithms of decision tree optimization for various complexity measures. A corollary connected with combinatorial geometry is considered.",

keywords = "Complexity, Decision tree, Information system, Optimization",

author = "Moshkov, {Mikhail Ju}",

year = "2007",

month = oct,

day = "28",

doi = "10.1016/j.disc.2007.03.002",

language = "English (US)",

volume = "307",

pages = "2837--2844",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "22",

}

TY - JOUR

T1 - On the class of restricted linear information systems

AU - Moshkov, Mikhail Ju

PY - 2007/10/28

Y1 - 2007/10/28

N2 - In the paper the class of restricted linear information systems is described completely. For decision tables over each such information system there exist low upper bounds on minimal complexity of decision trees and polynomial algorithms of decision tree optimization for various complexity measures. A corollary connected with combinatorial geometry is considered.

AB - In the paper the class of restricted linear information systems is described completely. For decision tables over each such information system there exist low upper bounds on minimal complexity of decision trees and polynomial algorithms of decision tree optimization for various complexity measures. A corollary connected with combinatorial geometry is considered.

KW - Complexity

KW - Decision tree

KW - Information system

KW - Optimization

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

U2 - 10.1016/j.disc.2007.03.002

DO - 10.1016/j.disc.2007.03.002

M3 - Article

AN - SCOPUS:35449005175

SN - 0012-365X

VL - 307

SP - 2837

EP - 2844

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 22

ER -

On the class of restricted linear information systems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this