Efficient Modal Decision Trees

Modal symbolic learning is an emerging machine learning paradigm for (non)-tabular data, and modal decision trees are its most representative schema. The underlying idea behind modal symbolic learning is that non-tabular (e.g., temporal, spatial, spatial-temporal) instances can be seen as finite Kripke structures of a suitable modal logic and propositional alphabet; from a non-tabular dataset, then, modal formulas can be extracted to solve classic tasks such as classification, regression, and association rules extraction. Although this paradigm has already been proven successful in different learning tasks, a provably correct and complete formulation of modal decision trees has only recently been found. In this paper, we prove that correct and complete modal decision trees are also efficient, learning-wise.