4 papers · 1 filter
Generating in the Limit with Infinitely Many Hallucinations
Irene Strauss, Alexandra Butoi, Ryan Cotterell
The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner task…
Training Neural Networks as Recognizers of Formal Languages
Alexandra Butoi, Ghazal Khalighinejad, Anej Svete +3
Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds…
On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
Franz Nowak, Anej Svete, Alexandra Butoi +1
The performance of modern language models (LMs) has been improved by chain-of-thought (CoT) reasoning, i.e., the process of generating intermediate results that guide the model tow…
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
Alexandra Butoi, Tim Vieira, Ryan Cotterell +1
The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of a context-free grammar (CFG) or pushdown automaton (PDA) controlling anoth…