Learning Weak Monadic Second-Order Logical Formulas from Queries and Counterexamples(Complexity Theory and Related Topics)
Tetsuro Nishino · Kyoto University Research Information Repository (Kyoto University) · 1990
In this paper, we consider the problem of learning an unknown weak monadic second-order (WMS for short) logical formula from examples making it true and those making it false.It is well known that, for a WMS formula, there exists a deterministic frontier-to-root tree automaton (dfrta for short $)$ accepting the trees which are the encodings of those examples making the formula true.Thus, we reduce our problem to the problem of learning an unknown tree language from examples of its members and nonmembers.We assume that the tree language is presented by the Angluin's minimally ade- quate teacher, which can answer membership queries and equivalence queries.Our learning algorithm $L_{T}^{*}$ to learn tree languages is based on a slight variant of the Sakakibara's polynomial time algorithm to learn deterministic skeletal automata.The algorithm $L_{T}^{*}$ runs in time polynomial in the number of states of the minimum dfrta for the unknown tree language and the maximum size of any counterexample provided by the teacher.Thus we propose a new framework of concept learning in which atomic relations such as $"\subseteq$ and many relations definable by WMS formulas, e.g.prefix-closedness of sets, can be learned in polynomial time.Definition 2.1 A $\Sigma$ -tree, or a tree over $\Sigma$ is a mapping $t$ from $Dom(t)$ into $\Sigma$ , where $Dom(t)$ is a finite subset of $N^{*}$ satisfying :1.If $x\in Dom(t)$ and $x\succ y$ then $y\in Dom(t)$ .3