4 papers
Preservation Theorems for Transducer Outputs
Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov +2
Suppose we have a deterministic finite-state transducer and an infinite word , and run on to obtain an infinite word . Which properties of are guaranteed t…
A dynamical view of Tijdeman's solution of the chairman assignment problem
Valérie Berthé, Olivier Carton, Nicolas Chevallier +2
In 1980, R. Tijdeman provided an on-line algorithm that generates sequences over a finite alphabet with minimal discrepancy, that is, such that the occurrence of each letter optima…
On the Decidability of Monadic Theories of Arithmetic Predicates
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld +3
We investigate the decidability of the monadic second-order (MSO) theory of the structure , for various unary predicates $P_1,\ldots,P…
Obstructions to return preservation for episturmian morphisms
Valérie Berthé, Herman Goulet-Ouellet
This paper studies obstructions to preservation of return sets by episturmian morphisms. We show, by way of an explicit construction, that infinitely many obstructions exist. This…