Learnability and definability in trees and similar structures (Q705070)

The problem of concept learning is to identify an unknown set from a given family of sets. A universe is a nonempty finite set \(A\). A vocabulary \(\tau\) is a finite set of predicates defined on \(A\). A structure is the pair (\(A,\tau\)). An atomic formula is \({x = y}\) or \({R(x_1,\dots ,x_r)}\), where \({R \in \tau}\). Formulas of first-order logic (FO) are built up from atomic formulas using Boolean operations and quantification over individual variables. Monadic-second order logic (MSO) is the extension of FO by monadic predicates \({X(x)}\) defined on \(A\) and quantification over predicate variables. The elements \({b_1,\dots ,b_l}\) from \(A\) in the formula \(\varphi({x_1,\dots ,x_k, b_1,\dots ,b_l})\) are parameters. A concept class is a family \(\mathcal{C} \subseteq 2^V\) of subsets of a set \(V\). Let \({U \subseteq V}\) and \(\mathcal{C} \cap U = \{C \cap U \mid C \in\mathcal{C}\}\). The set \(U\) is shattered by \(\mathcal{C}\) if \(\mathcal{C} \cap U = 2^U\). The Vapnik-Chervonenkis dimension, or VC-dimension VC(\(\mathcal{C}\)) of \(\mathcal{C}\) is the maximum of the sizes of the shattered subsets of \(V\). It is shown: 1) MSO formulas (FO formulas) with parameters have bounded VC-dimension over structures of bounded clique-width (local clique-width); 2) MSO formulas of a fixed size have bounded strong consistency dimension over MSO formulas of a fixed larger size, for labelled finite trees; 3) these bounds imply positive learnability results for Probably Approximately Correct (PAC) learning. The proofs are based on bounds for related definability problems for finite automata over labelled trees.