Learning intersection-closed classes with signatures

Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature.

Authors

• Andrei Bulatov
• Hubie Chen
• Víctor Dalmau

Keywords

• Computational learning
• Closure algorithm
• Polymorphism
• Quantified formulas