3 citations · 3 across the 8 of their papers we have counts for
8 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 a…
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 open…
The Regular Languages of First-Order Logic with One Alternation
Corentin Barloy, Michaël Cadilhac, Charles Paperman +1
The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary formula de…
Bidimensional linear recursive sequences and universality of unambiguous register automata
Corentin Barloy, Lorenzo Clemente
We study the universality and inclusion problems for register automata over equality data. We show that the universality and the inclusion problems can be solved with 2-EXPTIME com…
A Robust Class of Linear Recurrence Sequences
Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote +1
We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show…