Totally optimal decision trees for Boolean functions

DOI10.1016/J.DAM.2016.07.009MaRDI QIDQ323025zbMATH OpenOpenAlexFDO

Authors Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Publication date 7 October 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.07.009

zbMATH Keywords

Boolean functionsspace complexitytime complexitymonotone Boolean functionstotally optimal decision trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Experimental study of totally optimal decision trees
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Totally optimal decision rules
• scientific article; zbMATH DE number 741345
• scientific article; zbMATH DE number 3866582

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 1983159 (Why is no real title available?)
• scientific article; zbMATH DE number 5497553 (Why is no real title available?)
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Average time complexity of decision trees.
• Complexity measures and decision tree complexity: a survey.
• Computational complexity of Boolean functions
• Constructing optimal binary decision trees is NP-complete
• Exact learning when irrelevant variables abound
• Innovations in intelligent machines. 4. Recent advances in knowledge engineering
• On recognizing graph properties from adjacency matrices
• Optimal Binary Identification Procedures
• Optimization and analysis of decision trees and rules: dynamic programming approach
• Optimizing decision trees through heuristically guided search
• Pareto-optimal patterns in logical analysis of data
• Reducibility among combinatorial problems
• The synthetic approach to decision table conversion
• Time-space tradeoffs for branching programs
• Transactions on Rough Sets III

Cited in

(8)

• Multi-stage optimization of decision and inhibitory trees for decision tables with many-valued decisions
• Time and space complexity of deterministic and nondeterministic decision trees
• Bi-criteria optimization of decision trees with applications to data analysis
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Experimental study of totally optimal decision trees
• scientific article; zbMATH DE number 1379304 (Why is no real title available?)
• On boolean decision trees with faulty nodes
• Conversational recommendation: theoretical model and complexity analysis

Describes a project that uses

Uses Software

• JBool
• DAGGER

This page was built for publication: Totally optimal decision trees for Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q323025)