Weakly unambiguous morphisms

详细信息    查看全文

• 作者：Dominik D. Freydenberger ; Hossein Nevisi ; Daniel Reidenbach
• 关键词：Nonerasing morphisms ; Ambiguity
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：24 August, 2012
• 年：2012
• 卷：448
• 期：Complete
• 页码：21-40
• 全文大小：342 K

文摘

A nonerasing morphism is said to be weakly unambiguous with respect to a word if is the only nonerasing morphism that can map to , i.e., there does not exist any other nonerasing morphism satisfying . In the present paper, we wish to characterise those words with respect to which there exists such a morphism. This question is nontrivial if we consider so-called length-increasing morphisms, which map a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions.