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.

Submitted, 2023. 32 pages.

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