On compressible information systems

Mikhail Moshkov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations


In the paper infinite information systems are investigated which are used in pattern recognition, discrete optimization, and computational geometry. An information system is called compressible relatively to a weight function if for each problem with enough big weight (total weight of attributes in problem description) there exists a decision tree which solves this problem and which weighted depth is less than the problem weight. In the paper all pairs of information systems and weight functions are described such that the information system is compressible relatively to the weight function.

Original languageEnglish (US)
Title of host publicationRough Sets and Current Trends in Computing - 3rd International Conference, RSCTC 2002, Proceedings
EditorsJames J. Alpigini, James F. Peters, Andrzej Skowron, Ning Zhong
PublisherSpringer Verlag
Number of pages5
ISBN (Print)9783540442745
StatePublished - 2002
Externally publishedYes
Event3rd International Conference on Rough Sets and Current Trends in Computing, RSCTC 2002 - Malvern, United States
Duration: Oct 14 2002Oct 16 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Rough Sets and Current Trends in Computing, RSCTC 2002
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On compressible information systems'. Together they form a unique fingerprint.

Cite this