License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.213
URN: urn:nbn:de:0030-drops-30123
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3012/
Go to the corresponding LIPIcs Volume Portal

Freydenberger, Dominik D. ; Nevisi, Hossein ; Reidenbach, Daniel

Weakly Unambiguous Morphisms

pdf-format:
22.pdf (0.6 MB)

Abstract

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

@InProceedings{freydenberger_et_al:LIPIcs:2011:3012,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2011/3012},
  URN =		{urn:nbn:de:0030-drops-30123},
  doi =		{10.4230/LIPIcs.STACS.2011.213},
  annote =	{Keywords: Combinatorics on words, Morphisms, Ambiguity}
}

Keywords: Combinatorics on words, Morphisms, Ambiguity
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI