Results 111 to 120 of about 6,397 (149)
Some of the next articles are maybe not open access.
Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version)
Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82, 1982This work generalizes decision trees in order to model algorithms which allow probabilistic, nondeterministic, or alternating control. Two geometric techniques for proving lower bounds on the time required by ordinary decision trees (Dobkin and Lipton's -&-ldquo;region-counting-&-rdquo; technique as applied to the knapsack and element uniqueness ...
Udi Manber, Martin Tompa
openaire +1 more source
Deterministic and Nondeterministic Decision Trees for Rough Computing
Fundamenta Informaticae, 2000In the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated.
openaire +2 more sources
The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
Journal of the ACM, 1985This work generalizes decision trees in order to study lower bounds on the running times of algorithms that allow probabilistic, nondeterministic, or alternating control. It is shown that decision trees that are allowed internal randomization (at the expense of introducing a small probability of error) run no faster asymptotically than ordinary ...
Manber, Udi, Tompa, Martin
openaire +2 more sources
COMPARITIVE ANALYSIS OF DETERMINISTIC AND NONDETERMINISTIC DECISION TREE COMPLEXITY. GLOBAL APPROACH
Fundamenta Informaticae, 1996We study the relationships between the complexity of a task description and the minimal complexity of deterministic and nondeterministic decision trees solving this task. We investigate decision trees assuming a global approach i.e. arbitrary checks from a given check system can be used for constructing decision trees.
openaire +2 more sources
Comparative Analysis of Deterministic and Nondeterministic Decision Trees
2020This book compares four parameters of problems in arbitrary information systems: complexity of problem representation and complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees for problem solving. Deterministic decision trees are widely used as classifiers, as a means of knowledge representation, and as algorithms.
openaire +2 more sources
2020
In this chapter, we consider bounds on the minimum complexity, an approach to proof of lower bounds, and algorithms for construction of nondeterministic and strongly nondeterministic decision trees. The bounds on complexity are true for arbitrary complexity functions.
openaire +1 more source
In this chapter, we consider bounds on the minimum complexity, an approach to proof of lower bounds, and algorithms for construction of nondeterministic and strongly nondeterministic decision trees. The bounds on complexity are true for arbitrary complexity functions.
openaire +1 more source
Time and Space Complexity of Deterministic and Nondeterministic Decision Trees: Local Approach
2023 IEEE International Conference on Big Data (BigData), 2023Kerven Durdymyradov, Mikhail Moshkov
openaire +1 more source
Integrative oncology: Addressing the global challenges of cancer prevention and treatment
Ca-A Cancer Journal for Clinicians, 2022Jun J Mao,, Msce +2 more
exaly