Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Freydenberger, Dominik D.; Nevisi, Hossein; Reidenbach, Daniel License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-30123

; ;

Weakly Unambiguous Morphisms



A nonerasing morphism sigma is said to be weakly unambiguous with respect to a word w if sigma is the only nonerasing morphism that can map w to sigma(w), i.e., there does not exist any other nonerasing morphism tau satisfying tau(w) = sigma(w). 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.

BibTeX - Entry

  author =	{Dominik D. Freydenberger and Hossein Nevisi and Daniel Reidenbach},
  title =	{{Weakly Unambiguous Morphisms}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{213--224},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-30123},
  doi =		{},
  annote =	{Keywords: Combinatorics on words, Morphisms, Ambiguity}

Keywords: Combinatorics on words, Morphisms, Ambiguity
Seminar: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Related Scholarly Article:
Issue date: 2011
Date of publication: 2011

DROPS-Home | Fulltext Search | Imprint Published by LZI