arXiv preprint ·
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Formal Languages & Automata
Provably Tractable NFA-Constrained Language Generation via HMMs
Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
Small universal multiset reaction systems
Testing and Learning Symbolic Finite State Machines
From Transformers to Weighted Automata: Towards the Verification of Large Language Models
Get the few papers worth your time in Formal Languages & Automata every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.