Automatic sequences are also non-uniformly morphic

DOI10.1007/978-3-030-55857-4_1zbMATH Open1485.68202arXiv1910.08546OpenAlexW2981143402MaRDI QIDQ2232027FDOQ2232027

Authors: Jean-Paul Allouche, Jeffrey Shallit 

Publication date: 4 October 2021

Abstract: It is well-known that there exist infinite sequences that are the fixed point of non-uniform morphisms, but not $k$-automatic for any $k$. In this note we show that every $k$-automatic sequence is the image of a fixed point of a {it non-uniform/} morphism.

Full work available at URL: https://arxiv.org/abs/1910.08546

Recommendations

• ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
• scientific article; zbMATH DE number 1187480
• On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
• Hidden automatic sequences
• How to prove that a sequence is not automatic

zbMATH Keywords

fixed pointautomatic sequencecodinguniform morphismconstant length

Mathematics Subject Classification ID

Combinatorics on words (68R15) Automata sequences (11B85)

Cited In (9)

• Morphic sequences versus automatic sequences
• Automaton mappings of periodic sequences not multiplying distortions
• Block-counting sequences are not purely morphic
• GAPS IN THE THUE–MORSE WORD
• Mix-automatic sequences
• Hidden automatic sequences
• Automatic abelian complexities of Parikh-collinear fixed points
• Letter frequency vs factor frequency in pure morphic words
• Automaticity and Parikh-Collinear Morphisms

This page was built for publication: Automatic sequences are also non-uniformly morphic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232027)