For which unary predicates P1, …, Pm is the MSO theory of the structure ❬N; <, P1, …, Pm❭ 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 Pi 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.