Chain Length and CSPs Learnable with Few Queries


  • Christian Bessiere CNRS
  • Cl‚ément Carbonnel CNRS
  • George Katsirelos INRA



The goal of constraint acquisition is to learn exactly a constraint network given access to an oracle that answers truthfully certain types of queries. In this paper we focus on partial membership queries and initiate a systematic investigation of the learning complexity of constraint languages. First, we use the notion of chain length to show that a wide class of languages can be learned with as few as O(n log(n)) queries. Then, we combine this result with generic lower bounds to derive a dichotomy in the learning complexity of binary languages. Finally, we identify a class of ternary languages that eludes our framework and hints at new research directions.




How to Cite

Bessiere, C., Carbonnel, C., & Katsirelos, G. (2020). Chain Length and CSPs Learnable with Few Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1420-1427.



AAAI Technical Track: Constraint Satisfaction and Optimization