6 citations · 7 across the 12 of their papers we have counts for
11 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…
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…
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…
Dynamic Membership for Regular Languages
Antoine Amarilli, Louis Jachiet, Charles Paperman
We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this str…
Locality and Centrality: The Variety ZG
Antoine Amarilli, Charles Paperman
We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect p…
On polynomial recursive sequences
Michaël Cadilhac, Filip Mazowiecki, Charles Paperman +2
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the…
Continuity of Functional Transducers: A Profinite Study of Rational Functions
Michaël Cadilhac, Olivier Carton, Charles Paperman
A word-to-word function is continuous for a class of languages~ if its inverse maps _languages to~. This notion provides a basis for an algeb…
Regular Separability of Parikh Automata
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota +1
We investigate a subclass of languages recognized by vector addition systems, namely languages of nondeterministic Parikh automata. While the regularity problem (is the language of…
Separability of Reachability Sets of Vector Addition Systems
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota +1
Given two families of sets and , the separability problem for asks whether for two given sets there ex…