Automatic sequences: from rational bases to trees

The $n$th term of an automatic sequence is the output of a deterministicfinite automaton fed with the representation of $n$ in a suitable numerationsystem. In this paper, instead of considering automatic sequences built on anumeration system with a regular numeration language, we consider those builton languages associated with trees having periodic labeled signatures and, inparticular, rational base numeration systems. We obtain two maincharacterizations of these sequences. The first one is concerned with $r$-blocksubstitutions where $r$ morphisms are applied periodically. In particular, weprovide examples of such sequences that are not morphic. The secondcharacterization involves the factors, or subtrees of finite height, of thetree associated with the numeration system and decorated by the terms of thesequence.Comment: 26 pages, 16 figures; final version accepted for publication in Discrete Mathematics & Theoretical Computer Scienc