10 citations · 17 across the 10 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
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…