Subword occurrences, weighted automata and iterated morphisms, especially the Fibonacci morphism (Q428858): Difference between revisions

The author studies ``subwords'' (in the sense ``scattered subwords'') of (in)finite words obtained by iterating a morphism of the free monoids. With each such (nonerasing) morphism the author associates a weighted directed graph that can be seen as a weighted automaton, which is used to compute the number of occurrences of a word as a scattered subword in the iterated image of some given word under the morphism. Explicit formulas can be obtained using the theory of integral sequential word functions. The author gives an application to the Fibonacci morphism \(a\to ab\), \(b\to a\).