Learning Unions of Intersecting Affine Modules in One Dimension with Queries

We study the exact learnability of finite unions of intersecting affine modules in one dimension. An affine module is a set of the form $a+{\sum }_{j=1}^s{b}_j\mathbb{Z}$, where $a,b_1,\dots ,b_s\in \mathbb{N}$. We say that a set definable as a finite union of affine modules is a union of intersecting affine modules if it admits a representation in which all modules have a non-empty intersection. We show that this class is efficiently exactly learnable using equivalence and subset queries. Moreover, subset queries can be replaced with membership queries when a common element is known. Our algorithm requires at most $k\log (2\mathrm{\mid }{x}_{\mathrm{\ell }}\mathrm{\mid })+2k$ counterexamples, where $k$ is the number of affine modules in the smallest representation and $x_{\mathrm{\ell }}$ is the largest counterexample. This implies polynomial-time learnability in the binary representation.