Weakly unambiguous morphisms (Q442106)

In this very interesting paper, the authors focus on a fundamental and desirable property of morphisms called weak unambiguity. More precisely, they examine the problem that, given a pattern \(\alpha \in \mathbb{N}^+\), whether there exists a length-increasing nonerasing morphism \(\sigma: \mathbb{N}^+ \rightarrow \Sigma^+\) that is weakly unambiguous with respect to \(\alpha\), i.e., there does not exist a nonerasing morphism \(\tau: \mathbb{N}^+ \rightarrow \Sigma^+\) that satisfies \(\tau(\alpha)=\sigma(\alpha)\) and, for some variable \(q\) in \(\alpha\), \(\tau(q)\neq \sigma(q)\). They show that the existence of such a morphism \(\sigma\) is dependent on the size of the target alphabet \(\Sigma\). For \(|\Sigma|\geq 3\), the authors give a compact and efficiently decidable characteristic condition. For \(|\Sigma|=2\), they give sufficient or necessary conditions but leave the decidability problem open. For \(|\Sigma|=1\), they show that the existence depends on some particular equations related to the number of variables in \(\alpha\) that need to be satisfied.