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…
A Factorization Theorem for Forest Algebras
Shaull Almagor, Michaël Cadilhac, Asaf Shoham
Simon's factorization theorem is a celebrated tool in algebraic automata theory, providing bounded-depth decompositions of words with respect to morphisms into finite semigroups. W…
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…
Two-Way One-Counter Nets Revisited
Shaull Almagor, Michaël Cadilhac, Asaf Yeshurun
One Counter Nets (OCNs) are finite-state automata equipped with a counter that cannot become negative, but cannot be explicitly tested for zero. Their close connection to various o…