5 papers
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…
Shuffles of Context-Free Languages along Regular Trajectories
Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund
In single-core processors, concurrency requires that multiple processes be interleaved into a single thread of execution by a scheduler. The language-theoretic operation that corre…
Algebraic Characterizations of Classes of Regular Languages in DynFO
Corentin Barloy, Felix Tschirbs, Nils Vortmeier +1
This paper explores the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of…
Dynamic Membership for Regular Tree Languages
Antoine Amarilli, Corentin Barloy, Louis Jachiet +1
We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet and a regular tree language over (expressed, e.g., as…
The Alternation Hierarchy of First-Order Logic on Words is Decidable
Corentin Barloy, Michaël Cadilhac, Charles Paperman +1
We show that for any , it is decidable, given a regular language, whether it is expressible in the fragment of first-order logic FO[<]. This settles a question ope…