Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.06093 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915020704579584 |
|---|---|
| author | Ostonov, Azimkhon Moshkov, Mikhail |
| author_facet | Ostonov, Azimkhon Moshkov, Mikhail |
| contents | In this paper, we consider classes of decision tables with 0-1-decisions closed relative to removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study the dependence of the minimum complexity of deterministic decision trees on various parameters of the tables: the minimum complexity of a test, the complexity of the set of attributes attached to columns, and the minimum complexity of a strongly nondeterministic decision tree. We also study the dependence of the minimum complexity of strongly nondeterministic decision trees on the complexity of the set of attributes attached to columns. Note that a strongly nondeterministic decision tree can be interpreted as a set of true decision rules that cover all rows labeled with the decision 1. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_06093 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes Ostonov, Azimkhon Moshkov, Mikhail Computational Complexity In this paper, we consider classes of decision tables with 0-1-decisions closed relative to removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study the dependence of the minimum complexity of deterministic decision trees on various parameters of the tables: the minimum complexity of a test, the complexity of the set of attributes attached to columns, and the minimum complexity of a strongly nondeterministic decision tree. We also study the dependence of the minimum complexity of strongly nondeterministic decision trees on the complexity of the set of attributes attached to columns. Note that a strongly nondeterministic decision tree can be interpreted as a set of true decision rules that cover all rows labeled with the decision 1. |
| title | Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2305.06093 |