The unambiguity of segmented morphisms

This paper studies the ambiguity of morphisms in free monoids. A morphism σσ is said to be ambiguous with respect to a string αα if there exists a morphism ττ which differs from σσ for a symbol occurring in αα, but nevertheless satisfies τ(α)=σ(α)τ(α)=σ(α); if there is no such ττ then σσ is called unambiguous. Motivated by the recent initial paper on the ambiguity of morphisms, we introduce the definition of a so-called segmented morphism σnσn, which, for any n∈Nn∈N, maps every symbol in an infinite alphabet onto a word that consists of nn distinct factors in ab+a, where a and b are different letters. For every nn, we consider the set U(σn)U(σn) of those finite strings over an infinite alphabet with respect to which σnσn is unambiguous, and we comprehensively describe its relation to any U(σm)U(σm), m≠nm≠n.Thus, our work features the first approach to a characterisation of sets of strings with respect to which certain fixed morphisms are unambiguous, and it leads to fairly counter-intuitive insights into the relations between such sets. Furthermore, it shows that, among the widely used homogeneous morphisms, most segmented morphisms are optimal in terms of being unambiguous for a preferably large set of strings. Finally, our paper yields several major improvements of crucial techniques previously used for research on the ambiguity of morphisms.