6 citations · 7 across the 12 of their papers we have counts for
4 papers · 1 filter
Conditional Membership in Regular Languages
Antoine Amarilli, Sebastien Felipe Labbe, Charles Paperman
We study a formulation of regular language membership as a promise problem, which we dub conditional membership: we fix a promise language and a target language …
Algebraic Decomposition Theory for Transformer Length Generalization
Andy Yang, Blerta Veseli, Corentin Barloy +5
Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit lengt…
Earliest query answering over streamed trees
Mateusz Gienieczko, Martín Muñoz, Filip Murlak +1
Streaming allows executing queries over massive JSON or XML documents whose size makes it infeasible to fully parse them into a tree. Earliest query answering is a radical approach…
Out-of-Order Membership in Regular Languages
Antoine Amarilli, Sebastien Labbe, Charles Paperman
We introduce the task of out-of-order membership to a formal language L, where the letters of a word w are revealed one by one in an adversarial order. The length |w| is known in a…