On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes

In this paper, we consider classes of conventional decision tables closed relative to the 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 and nondeterministic decisi...

Descripción completa

Detalles Bibliográficos
Autores principales: Ostonov, Azimkhon, Moshkov, Mikhail
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2023
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10606725/
https://www.ncbi.nlm.nih.gov/pubmed/37895532
http://dx.doi.org/10.3390/e25101411
_version_ 1785127384711692288
author Ostonov, Azimkhon
Moshkov, Mikhail
author_facet Ostonov, Azimkhon
Moshkov, Mikhail
author_sort Ostonov, Azimkhon
collection PubMed
description In this paper, we consider classes of conventional decision tables closed relative to the 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 and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We also study the dependence of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that a nondeterministic decision tree can be interpreted as a set of true decision rules that covers all rows of the table.
format Online
Article
Text
id pubmed-10606725
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-106067252023-10-28 On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes Ostonov, Azimkhon Moshkov, Mikhail Entropy (Basel) Article In this paper, we consider classes of conventional decision tables closed relative to the 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 and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We also study the dependence of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that a nondeterministic decision tree can be interpreted as a set of true decision rules that covers all rows of the table. MDPI 2023-10-03 /pmc/articles/PMC10606725/ /pubmed/37895532 http://dx.doi.org/10.3390/e25101411 Text en © 2023 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Ostonov, Azimkhon
Moshkov, Mikhail
On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title_full On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title_fullStr On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title_full_unstemmed On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title_short On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
title_sort on complexity of deterministic and nondeterministic decision trees for conventional decision tables from closed classes
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10606725/
https://www.ncbi.nlm.nih.gov/pubmed/37895532
http://dx.doi.org/10.3390/e25101411
work_keys_str_mv AT ostonovazimkhon oncomplexityofdeterministicandnondeterministicdecisiontreesforconventionaldecisiontablesfromclosedclasses
AT moshkovmikhail oncomplexityofdeterministicandnondeterministicdecisiontreesforconventionaldecisiontablesfromclosedclasses

Ejemplares similares