Loughborough University
Browse
Nevisi_Reidenbach_DLT_2012_Conference_version.pdf (319.54 kB)

Morphic primitivity and alphabet reductions

Download (319.54 kB)
conference contribution
posted on 2012-07-25, 14:10 authored by Hossein NevisiHossein Nevisi, Daniel Reidenbach
An 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 2012

Version

  • AM (Accepted Manuscript)

Publication date

2012

Notes

The final publication is available at www.springerlink.com.

ISBN

978-3-642-31652-4

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes In Computer Science;7410

Language

  • en