Learning Term Rewriting Systems from Entailment .
Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa · 2000
. Learning from entailment is a learning model suitable for learning firstorder formulas, in which examples are formulas in the first-order language which are implied or not implied. In this paper, we study the learnability of term rewriting systems in this framework. A term rewriting system is a simple model of tree transduction used for semi-structured data and Web, which can be considered as a fragment of firstorder equational logic with a binary predicate ). First, we present a generic algorithm using entailment equivalence queries and request for hint queries, and show that the class of terminating term rewriting systems is exactly learnable by this algorithm. Next, we present a polynomial time learning algorithm using entailment equivalence and entailment membership queries for another subclass k-variable linear tree translations with top-down rewriting strategy. 1 Introduction In this paper, we study the learnability of functions and relations represented by term rew...