The Ambiguity of Morphisms in Free Monoids and its Impact on Algorithmic Properties of Pattern Languages

This book systematically discusses a basic problem in combinatorics on words: the ambiguity of morphisms, i. e. the question of whether, for any finite string s and any given morphism h, there is another morphism g satisfying g(s)=h(s). These studies yield a characterisation of those strings for which there exists an unambiguous morphism; furthermore, they lead to various insights into the ambiguity of important selected example morphisms. Additional considerations are concerned with the ambiguity of so-called terminal-preserving morphisms.

Due to its fundamental nature, the ambiguity of morphisms shows strong connections to other topics in discrete mathematics and computer science such as pattern inference and equality sets; in particular, it is significantly related to various properties of E-pattern languages. Therefore, the book provides a thorough survey on pattern languages and presents several profound advances in the understanding of this subject.