Metraipolis › archive › dc_3be15f736dc1

Learning Shuffle Ideals with Membership Queries and Contrastive Examples — arXiv:2609.32820

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.32820
License (as archived): CC0-1.0
Archived: 2026-10-07T22:39:50.138Z
SHA-256 of the archived text: b79bd55909214574e7b30c78c65a56daf0073143a53bcc5acfa0dae070a45e94
Stable URL of this page: https://metraipolis.com/documento/dc_3be15f736dc1

How to cite

Learning Shuffle Ideals with Membership Queries and Contrastive Examples — arXiv:2609.32820 — arXiv (en), https://arxiv.org/abs/2609.32820 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3be15f736dc1 (Metraipolis archive dc_3be15f736dc1, sha256 b79bd55909214574e7b30c78c65a56daf0073143a53bcc5acfa0dae070a45e94)

BibTeX

@misc{dc3be15f736dc1,
  title = {Learning Shuffle Ideals with Membership Queries and Contrastive Examples — arXiv:2609.32820},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32820},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3be15f736dc1; sha256 b79bd55909214574e7b30c78c65a56daf0073143a53bcc5acfa0dae070a45e94},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32820. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word $w$ is in the target language or not, but also provides a most similar word $w'$ that belongs to the target language if %and only if $w$ does not. For both settings, it is shown that even some very simple classes of shuffle ideals cannot be learned efficiently. By contrast, we obtain positive learnability results for classes of shuffle ideals that meet certain structural conditions. In the case of membership queries, these structural conditions are related to the previously studied notion of universal words, and raise new questions in word combinatorics. In the case of contrastive queries, the structural conditions relate to partitioning sets of words that are listed in shortlex order.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.32820 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:14:28.653Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).