Nevisi_Reidenbach_DLT_2012_Conference_version.pdf (319.54 kB)
Download fileMorphic primitivity and alphabet reductions
conference contribution
posted on 2012-07-25, 14:10 authored by Hossein NevisiHossein Nevisi, Daniel ReidenbachAn alphabet reduction is a 1-uniform morphism that maps
a word to an image that contains a smaller number of dfferent letters.
In the present paper we investigate the effect of alphabet reductions on
morphically primitive words, i. e., words that are not a fixed point of
a nontrivial morphism. Our first main result answers a question on the
existence of unambiguous alphabet reductions for such words, and our
second main result establishes whether alphabet reductions can be given
that preserve morphic primitivity. In addition to this, we study Billaud's
Conjecture - which features a dfferent type of alphabet reduction, but
is otherwise closely related to the main subject of our paper - and prove
its correctness for a special case.
History
School
- Science
Department
- Computer Science
Citation
NEVISI, H. and REIDENBACH, D., 2012. Morphic primitivity and alphabet reductions. IN: Yen, H.-C. and Ibarra, O.H. (eds.). Developments in Language Theory: 16th International Conference, DLT 2012 Taipei, Taiwan, August 14-17, 2012 Proceedings. Lecture Notes In Computer Science; 7410, pp. 440-451.Publisher
© Springer-Verlag Berlin Heidelberg 2012Version
- AM (Accepted Manuscript)
Publication date
2012Notes
The final publication is available at www.springerlink.com.ISBN
978-3-642-31652-4ISSN
0302-9743eISSN
1611-3349Publisher version
Book series
Lecture Notes In Computer Science;7410Language
- en