Comparative Analysis of Deterministic and Nondeterministic Decision Trees for Decision Tables from Closed Classes [PDF]
EntropyIn this paper, we consider classes of decision tables with many-valued decisions closed under operations of the removal of columns, the changing of decisions, the permutation of columns, and the duplication of columns.
Azimkhon Ostonov, Mikhail Moshkov
doaj +8 more sources
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity [PDF]
Information Processing Letters, 2010 A Direct Sum Theorem holds in a model of computation, when solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all ...
Ambainis +9 more
core +9 more sources
On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes [PDF]
Entropy, 2023 In this paper, we consider classes of conventional decision tables closed relative to the removal of attributes (columns) and changing decisions assigned to rows.
Azimkhon Ostonov, Mikhail Moshkov
doaj +5 more sources
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs [PDF]
, 2019 This paper studies propositional proof systems in which lines are sequents of decision trees or branching programs, deterministic or non-deterministic.
Buss, Sam, Das, Anupam, Knop, Alexander
core +11 more sources
Efficient Modeling of Deterministic Decision Trees for Recognition of Realizable Decision Rules: Bounds on Weighted Depth [PDF]
AxiomsIn this paper, an efficient algorithm for modeling the operation of a DDT (Deterministic Decision Tree) solving the problem of realizability of DRs (Decision Rules) is proposed and analyzed.
Kerven Durdymyradov, Mikhail Moshkov
doaj +3 more sources
Time and space complexity of deterministic and nondeterministic decision trees [PDF]
Annals of Mathematics and Artificial Intelligence, 2022 AbstractIn this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set called universe and an infinite set of two-valued functions (attributes) defined on the universe. We consider the notion of a problem over information system, which is described by a finite number of attributes and a mapping ...
Mikhail Moshkov
+6 more sources
Synthesis of Deterministic Top-down Tree Transducers from Automatic Tree Relations [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We consider the synthesis of deterministic tree transducers from automaton definable specifications, given as binary relations, over finite trees.
Christof Löding, Sarah Winter
doaj +11 more sources
Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes [PDF]
, 2023 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
Azimkhon Ostonov, Mikhail Moshkov
openalex +3 more sources
IEEE Access, 2023 This paper investigates classes of decision tables (DTs) with 0-1-decisions that are closed under the removal of attributes (columns) and changes to the assigned decisions to rows. For tables from any closed class (CC), the authors examine how the minimum complexity of deterministic decision trees (DDTs) depends on the minimum complexity of a strongly ...
Azimkhon Ostonov, Mikhail Moshkov
openalex +3 more sources
End-to-End Learning of Deterministic Decision Trees [PDF]
, 2019 Conventional decision trees have a number of favorable properties, including interpretability, a small computational footprint and the ability to learn from little training data. However, they lack a key quality that has helped fuel the deep learning revolution: that of being end-to-end trainable, and to learn from scratch those features that best ...
Thomas M. Hehn, Fred A. Hamprecht
openalex +4 more sources