Learning Union of Integer Hypercubes with Queries (with applications to monadic decomposition)

This archive is provided as artifact material for the article "Learning Union of Integer Hypercubes with Queries (with applications to monadic decomposition)" Accepted for publication at CAV2021. Abstract: We study the problem of learning a finite union of integer (axis-aligned) hypercubes over the d-dimensional integer lattice, i.e., whose edges are parallel to the coordinate axes. This is a natural generalization of the classic problem in the computational learning theory of learning rectangles. We provide a learning algorithm with access to a minimally adequate teacher (i.e. membership and equivalence oracles) that solves this problem in polynomial-time, for any fixed dimension d. Over a non-fixed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the field. We have also provided extensions to handle infinite hypercubes in the union, as well as showing how subset queries could improve the performance of the learning algorithm in practice. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a finite union of integer hypercubes correspond to a finite disjunction of monadic predicates over integer linear arithmetic (without modulos constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms. Instructions to run the .ova file: The password of the VM is "cav". 1. Download and install VirtualBox if you don’t have it already. 2. Open VirtualBox 3. Select File and Import Appliance 4. Select your OVA file in the import box and verify the settings in the center window 5. Make any changes if you need to in that center window (Recommended: 2 cores and 4GB RAM) 6. Click Import at the bottom. 7. Allow VirtualBox to import the file and configure it for us