{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T08:07:07Z","timestamp":1702454827220},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"02","license":[{"start":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T00:00:00Z","timestamp":1585872000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.aaai.org"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"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.<\/jats:p>","DOI":"10.1609\/aaai.v34i02.5499","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T18:56:32Z","timestamp":1593456992000},"page":"1420-1427","source":"Crossref","is-referenced-by-count":1,"title":["Chain Length and CSPs Learnable with Few Queries"],"prefix":"10.1609","volume":"34","author":[{"given":"Christian","family":"Bessiere","sequence":"first","affiliation":[]},{"given":"Cl\u0082\u00e9ment","family":"Carbonnel","sequence":"additional","affiliation":[]},{"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2020,4,3]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/5499\/5355","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/5499\/5355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,3]],"date-time":"2022-11-03T23:43:34Z","timestamp":1667519014000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/5499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,3]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2020,6,15]]}},"URL":"http:\/\/dx.doi.org\/10.1609\/aaai.v34i02.5499","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2020,4,3]]}}}
