Learning Unions of Intersecting Affine Modules in One Dimension with Queries

2026/06/27 by Eva González, Montserrat Hermo, Anthony Lin · 1 voice
Computer Science · #cs.DM

paper · pdf · doi:10.1145/3815436.3815448

arxiv published 2026/06/27 · arxiv updated 2026/07/15

Abstract

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+∑_j=1^sb_j ℤ, where a,b₁,…,b_s∈ℕ. 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 klog(2|x_ℓ|)+2k counterexamples, where k is the number of affine modules in the smallest representation and x_ℓ is the largest counterexample. This implies polynomial-time learnability in the binary representation.

Citations

• On Learning Polynomial Recursive Programs
• Learning Weighted Automata over Principal Ideal Domains
• Queries revisited
• Learning regular sets from queries and counterexamples
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
• A theory of the learnable

Discussions

• Eva Gonz\'alez, Montserrat Hermo, Anthony Lin: Learning Unions of Intersecting Affine Modules in One Dimension with Queries https://arxiv.org/abs/2606.29075 https://arxiv.org/pdf/2606.29075 https://ar [bsky, 0 points, 0 comments]

Related

• Algorithms for Checking Zero-Dimensional Complete Intersections
• Affine Algebras with Arbitrary Simple Modules
• Effective Detection of Nonsplit Module Extensions
• Polynomial Invariants for Affine Programs
• Principal intersection and bernstein-sato polynomial of an affine variety