Learning Inequated Range Restricted Horn Expressions

Abstract

A learning algorithm for the class of inequated range restricted Horn expressions is presented and proved correct. The main property of this class is that all the terms in the conclusion of a clause appear in the antecedent of the clause, possibly as subterms of more complex terms. And every clause includes in its antecedent all inequalities possible between all terms appearing in it. The algorithm works within the framework of learning from entailment, where the goal is to exactly identify some pre-fixed and unknown expression by making questions to membership and equivalence oracles.