3 papers
math.PR2026
Sofic measures
Marie-Pierre Béal, Vincent Jugé, Jean Mairesse +1
Sofic measures, also known as hidden Markov measures, have been extensively studied. In this paper, we survey some equivalent definitions of this notion and improve a bound for dec…
cs.FL2025
One-sided Hom shifts
Marie-Pierre Béal, Alexi Block Gorman
We prove that it is decidable whether a one-sided shift of finite type is conjugate to a one-sided Hom-shift, and whether a tree-shift of finite type is conjugate to a Hom tree-shi…
cs.DS2025
Checking and producing word attractors
Marie-Pierre Béal, Maxime Crochemore, Giuseppe Romana
The article focuses on word (or string) attractors, which are sets of positions related to the text compression efficiency of the underlying word. The article presents two combinat…