Restricted ambiguity of erasing morphisms

详细信息    查看全文

• 作者：Daniel Reidenbach^a ; ^{D.Reidenbach@lboro.ac.uk"" rel=""nofollow} ; Johannes C. Schneider^b ; ^{jschneider@informatik.uni-kl.de"" rel=""nofollow}
• 关键词：Erasing morphisms ; Ambiguity ; Pattern languages
• 刊名：Theoretical Computer Science
• 出版年：2011
• 出版时间：1 July 2011
• 年：2011
• 卷：412
• 期：29
• 页码：3510-3523
• 全文大小：334 K

文摘

A morphism h is called ambiguous for a string s if there is another morphism that maps s to the same image as h; otherwise, it is called unambiguous. In this paper, we examine some fundamental problems on the ambiguity of erasing morphisms. We provide a detailed analysis of so-called ambiguity partitions, and our main result uses this concept to characterise those strings that have a morphism of strongly restricted ambiguity. Furthermore, we demonstrate that there are strings for which the set of unambiguous morphisms, depending on the size of the target alphabet of these morphisms, is empty, finite or infinite. Finally, we show that the problem of the existence of unambiguous erasing morphisms is equivalent to some basic decision problems for nonerasing multi-pattern languages.