An automata theoretic decidability proof for first-order theory of \(\langle\mathbb{N},<,P\rangle\) with morphic predicate \(P\). (English) Zbl 0937.68078

Summary: We show connections between morphisms on words and pictures on a finite alphabet and finite deterministic incomplete automata. We use these connections to re-prove, in terms of automata, a decidability result about the first-order theory of the structures \(\langle \mathbb{N}, <, P\rangle\) for multi-ary morphic predicates \(P\).


68Q45 Formal languages and automata