The Monadic Theory of Toric Words

Abstract

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, 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.

Tribute to Arto Salomaa - A Towering Figure in Theoretical Computer Science