The monadic theory of toric words

For which unary predicates P₁, …, P_m is the MSO theory of the structure ❬N; <, P₁, …, P_m❭ decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morphic, and toric words. In doing so, we show that if each P_i can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. We give various applications of toric words, including decidability of the MSO theory of ❬N; <, {2ⁿ : n∈N}, {3ⁿ : n∈N}❭.

Submitted, 2023. 35 pages.

PDF © 2023 Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, and James Worrell.