ReidenbachSchneider_DLT10_RestrictedAmbiguityOfErasingMorphisms[1].pdf (193.48 kB)
Download fileRestricted ambiguity of erasing morphisms
conference contribution
posted on 2010-09-08, 15:20 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