The Monadic Theory of Toric Words

Valérie Berthé, Toghrul Karimov, Joël Ouaknine +2

For which unary predicates $P_1,\dots ,P_m$ is the MSO theory of the structure $⟨\mathbb{N};<,P_1,\dots ,P_m⟩$ decidable? We survey the state of the art, leadin…