10 citations · 17 across the 10 of their papers we have counts for
16 papers
Rational polynomial solvability reduces to stratifiability of semilinear sets
Michaël Cadilhac
A semilinear set is stratifiable if it is a finite union of linear sets whose periods have at most two nonzero coordinates, with no two periods in one component connecting alternat…
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…
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…
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…
Acacia-Bonsai: A Modern Implementation of Downset-Based LTL Realizability
Michaël Cadilhac, Guillermo A. Pérez
We describe our implementation of downset-manipulating algorithms used to solve the realizability problem for linear temporal logic (LTL). These algorithms were introduced by Filio…
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…
Rational subsets of Baumslag-Solitar groups
Michaël Cadilhac, Dmitry Chistikov, Georg Zetzsche
We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently…
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…
The Impatient May Use Limited Optimism to Minimize Regret
Michaël Cadilhac, Guillermo A. Pérez, Marie van den Bogaard
Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the ag…
Weak Cost Register Automata are Still Powerful
Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki +1
We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over with updates using and i…
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…
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…
Value Automata with Filters
Michaël Cadilhac, Andreas Krebs, Nutan Limaye
We propose to study value automata with filters, a natural generalization of regular cost automata to nondeterminism. Models such as weighted automata and Parikh automata appear na…
Bounded Parikh Automata
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and Ruess in 2003. Here, by means of related models, it is shown that the bounded languages recog…
On the expressiveness of Parikh automata and related models
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
The Parikh finite word automaton (PA) was introduced and studied by Klaedtke and Ruess in 2003. Natural variants of the PA arise from viewing a PA equivalently as an automaton that…