6 citations · 7 across the 12 of their papers we have counts for
18 papers
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…
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…
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…
Monadic Second-Order Logic with Arbitrary Monadic Predicates
Nathanaël Fijalkow, Charles Paperman
We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebra…
Topological Sorting under Regular Constraints
Antoine Amarilli, Charles Paperman
We introduce the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological so…
A Crevice on the Crane Beach: Finite-Degree Predicates
Michaël Cadilhac, Charles Paperman
First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB, and th…
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…
Finite-Degree Predicates and Two-Variable First-Order Logic
Charles Paperman
We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the orde…
Adding modular predicates to first-order fragments
Luc Dartois, Charles Paperman
We investigate the decidability of the definability problem for fragments of first order logic over finite words enriched with modular predicates. Our approach aims toward the most…