2023/09/19 by Hans Zantema, Zantema, Hans
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2309.10562
openalex publication_date 2023/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Morphic sequences form a natural class of infinite sequences, extending the well-studied class of automatic sequences. Where automatic sequences are known to have several equivalent characterizations and the class of automatic sequences is known to have several closure properties, for the class of morphic sequences similar closure properties are known, but only limited equivalent characterizations. In this paper we extend the latter. We discuss a known characterization of morphic sequences based on automata and we give a characterization of morphic sequences by finiteness of a particular class of subsequences. Moreover, we relate morphic sequences to rationality of infinite terms and describe them by infinitary rewriting.