Freydenberger, Dominik D. ;
Nevisi, Hossein ;
Reidenbach, Daniel
Weakly Unambiguous Morphisms
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 socalled lengthincreasing 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 lengthincreasing morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some noncharacteristic 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 = {213224},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3012},
URN = {urn:nbn:de:0030drops30123},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.213},
annote = {Keywords: Combinatorics on words, Morphisms, Ambiguity}
}
2011
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 