Time and space complexity of deterministic and nondeterministic decision trees
From MaRDI portal
Publication:2679423
DOI10.1007/s10472-022-09814-1OpenAlexW4295137004MaRDI QIDQ2679423
Publication date: 20 January 2023
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2201.01013
time complexitycomplexity classesspace complexitytime-space trade-offdeterministic decision treesnondeterministic decision trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Totally optimal decision trees for Boolean functions
- On topological lower bounds for algebraic computation trees
- Combinatorial machine learning. A rough set approach.
- Rudiments of rough sets
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Partial covers, reducts and decision rules in rough sets. Theory and applications
- Time-space trade-offs for branching programs
- Information systems theoretical foundations
- A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
- On the complexity of computations under varying sets of primitives
- An exponential lower bound on the size of algebraic decision trees for MAX
- Logical analysis of numerical data
- Time-space tradeoffs for branching programs
- Recent advances in the theory and practice of logical analysis of data
- A SAT-based approach to learn explainable decision sets
- Complexity measures and decision tree complexity: a survey.
- Independence number and the complexity of families of sets
- Three approaches to data analysis. Test theory, rough sets and logical analysis of data.
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- One-way functions and the nonisomorphism of NP-complete sets
- Foundations of Rule Learning
- Lower bounds for algebraic decision trees
- Multidimensional Searching Problems
- Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions
- Data Mining with Decision Trees
- Comparative Analysis of Deterministic and Nondeterministic Decision Tree Complexity Local Approach
- Transactions on Rough Sets III
- Decision tree complexity and Betti numbers
- Optimal classification trees
This page was built for publication: Time and space complexity of deterministic and nondeterministic decision trees
