1 Search Results for "Nevisi, Hossein"


Document
Weakly Unambiguous Morphisms

Authors: Dominik D. Freydenberger, Hossein Nevisi, and Daniel Reidenbach

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


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.

Cite as

Dominik D. Freydenberger, Hossein Nevisi, and Daniel Reidenbach. Weakly Unambiguous Morphisms. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 213-224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{freydenberger_et_al:LIPIcs.STACS.2011.213,
  author =	{Freydenberger, Dominik D. and Nevisi, Hossein and Reidenbach, Daniel},
  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 =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.213},
  URN =		{urn:nbn:de:0030-drops-30123},
  doi =		{10.4230/LIPIcs.STACS.2011.213},
  annote =	{Keywords: Combinatorics on words, Morphisms, Ambiguity}
}
  • Refine by Author
  • 1 Freydenberger, Dominik D.
  • 1 Nevisi, Hossein
  • 1 Reidenbach, Daniel

  • Refine by Classification

  • Refine by Keyword
  • 1 Ambiguity
  • 1 Combinatorics on words
  • 1 Morphisms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail