Decidability of the First-Order Theory of (ℕ;<,P) for Morphic Predicates P

We define a notion of morphism on multi-dimensional words on a finite alphabet $\Sigma$. We call ``morphic word'' a fixed point of such a morphism and we consider special kinds of morphic words (those that satisfy a notion called ``shape-symmetry''). The 1-dimensional morphic words always satisfy this notion. We show that given such a $\delta$-dimensional shape-symmetric fixed point P, the first order theory of the structure (N;<,0,PP) is decidable, when PP is the collection of $\delta$-ary predicates whose characteristic word is the image of P by a letter-to-letter application on the alphabet {0,1}. The proof is based on the same scheme as the usual proofs of decidability by finite automata, but is slightly more general. We give examples of non-shape-symmetric fixed points of morphisms leading to undecidable theories.