Learnability of Relatively Quantified Generalized Formulas Authors: Andrei Bulatov, Hubie Chen and Víctor Dalmau. Source: Lecture Notes in Artificial Intelligence Vol. 3244, 2004, 365 - 379. Abstract. In this paper we study the learning complexity of a vast class of quantifed formulas called Relatively Quantified Generalized Formulas. This class of formulas is parameterized by a set of predicates, called a basis. We give a complete classification theorem, showing that every basis gives rise to quantified formulas that are either polynomially learnable with equivalence queries, or not polynomially predictable with membership queries under some cryptographic assumption. We also provide a simple criteria distinguishing the learnable cases from the non-learnable cases. ©Copyright 2004 Springer