Abstract
In the paper infinite information systems are investigated which are used in pattern recognition,discrete optimization, computational geometry. The depth and the size of deterministic and nondeterministic decision trees over such information systems are studied. A partition of the set of all infinite information systems on two classes is considered. Systems from the first class are near to the best from the point of view of deterministic and nondeterministic decision tree time and space complexity. Decision trees for systems from the second class have in the worst case large time or space complexity. In proofs (which are too long and not included to the paper) methods of test theory [1, 2] and rough set theory [8,9] are used.
| Original language | English (US) |
|---|---|
| Title of host publication | Rough Sets and Current Trends in Computing - 2nd International Conference, RSCTC 2000, Revised Papers |
| Editors | Wojciech Ziarko, Yiyu Yao |
| Publisher | Springer Verlag |
| Pages | 199-203 |
| Number of pages | 5 |
| ISBN (Print) | 3540430741, 9783540430742 |
| DOIs | |
| State | Published - 2001 |
| Externally published | Yes |
| Event | 2nd International Conference on Rough Sets and Current Trends in Computing, RSCTC 2000 - Banff, Canada Duration: Oct 16 2000 → Oct 19 2000 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2005 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 2nd International Conference on Rough Sets and Current Trends in Computing, RSCTC 2000 |
|---|---|
| Country/Territory | Canada |
| City | Banff |
| Period | 10/16/00 → 10/19/00 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2001.
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science