Morphisms and almost-periodicity Original Research Article

We give a criterion, using oriented graphs, to decide whether an infinite word generated as fixed point of an expanding morphism on a finite alphabet is (effectively) almost-periodic. We present a non-almost-periodic system of almost-periodic predicates and deduce from it an example of structure 〈N;S, <,P〉, where P is a set of unary predicates, whose first-order theory is decidable but which does not admit quantifier elimination.