Zx. Chen et S. Homer, THE BOUNDED INJURY PRIORITY METHOD AND THE LEARNABILITY OF UNIONS OF RECTANGLES, Annals of pure and applied Logic, 77(2), 1996, pp. 143-168
We develop a bounded version of the finite injury priority method in r
ecursion theory. We use this to study the learnability of unions of re
ctangles over the domain {O,..., n - 1}(d) with only equivalence queri
es. Applying this method, we show three main results: (1) The class of
unions of rectangles is polynomial time learnable for constant dimens
ion d. (2) The class of unions of rectangles whose projections at some
unknown dimension are pairwise-disjoint is polynomial time learnable.
(3) The class of unions of two disjoint rectangles is polynomial time
learnable with unions of two rectangles as hypotheses.