A morphic word is obtained by iterating a morphism to generate an infinite word, and then applying a coding. We characterize morphic words with polynomial growth in terms of a new type of infinite word called a @math . A zigzag word is represented by an initial string, followed by a finite list of terms, each of which repeats for each @math in one of three ways: it grows forward [ @math , backward [ @math ], or just occurs once [ @math ]. Each term can recursively contain subterms with their own forward and backward repetitions. We show that an infinite word is morphic with growth @math iff it is a zigzag word of depth @math . As corollaries, we obtain that the morphic words with growth @math are exactly the ultimately periodic words, and the morphic words with growth @math are exactly the multilinear words.
@cite_0: 
@cite_3: We characterize the infinite words determined by one-way stack automata. An infinite language L determines an infinite word alpha if every string in L is a prefix of alpha. If L is regular or context-free, it is known that alpha must be ultimately periodic. We extend this result to the class of languages recognized by one-way nondeterministic checking stack automata (1-NCSA). We then consider stronger classes of stack automata and show that they determine a class of infinite words which we call multilinear. We show that every multilinear word can be written in a form which is amenable to parsing. Finally, we consider the class of one-way multihead deterministic finite automata (1:multi-DFA). We show that every multilinear word can be determined by some 1:multi-DFA, but that there exist infinite words determined by 1:multi-DFA which are not multilinear.
@cite_11: In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after which all of the predictor’s guesses are correct. In this paper we consider the case in which the predictor is an automaton and the emitted values are drawn from a finite set; i.e., the emitted sequence is an infinite word. We examine the predictive capabilities of finite automata, pushdown automata, stack automata (a generalization of pushdown automata), and multihead finite automata. We relate our predicting automata to purely periodic words, ultimately periodic words, and multilinear words, describing novel prediction algorithms for mastering these sequences.
The class of multilinear words appears in @cite_3 as the infinite words determined by one-way stack automata, and also in @cite_0 (as the reducts of the prime'' stream @math ). In @cite_11 , prediction of periodic words and multilinear words is studied in an automata-theoretic setting.