Chain Length and CSPs Learnable with Few Queries

Authors

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

DOI:

https://doi.org/10.1609/aaai.v34i02.5499

Abstract

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.

Downloads

Published

2020-04-03

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. https://doi.org/10.1609/aaai.v34i02.5499

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization