Freydenberger_Nevisi_Reidenbach_TCS_Weakly_unambiguous_morphisms_Final_version.pdf (429.43 kB)
Download fileWeakly unambiguous morphisms
journal contribution
posted on 25.07.2012, 14:35 by Dominik FreydenbergerDominik Freydenberger, Hossein NevisiHossein Nevisi, Daniel ReidenbachA nonerasing morphism σ is said to be weakly unambiguous with respect to a word s if σ is
the only nonerasing morphism that can map s to σ(s), i. e., there does not exist any other
nonerasing morphism τ satisfying τ(s) = σ(s). 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.
History
School
- Science
Department
- Computer Science