ReidenbachSchneider_TCS_Restricted_Ambiguity_of_Erasing_Morphisms_compact.pdf (211.28 kB)
Restricted ambiguity of erasing morphisms
journal contribution
posted on 2011-05-23, 15:33 authored by Daniel Reidenbach, Johannes C. SchneiderA 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.
History
School
- Science
Department
- Computer Science
Citation
REIDENBACH, D. and SCHNEIDER, J.C., 2011. Restricted ambiguity of erasing morphisms. Theoretical Computer Science, 412 (29), pp. 3510-3523.Publisher
© ElsevierVersion
- AM (Accepted Manuscript)
Publication date
2011ISSN
0304-3975Publisher version
Language
- en