Morphic Primitivity and Alphabet Reductions

详细信息    查看全文

• 作者：Hossein Nevisi (1) H.Nevisi@lboro.ac.uk
  Daniel Reidenbach (1) D.Reidenbach@lboro.ac.uk
• 关键词：Combinatorics on words – ; Morphisms – ; Ambiguity – ; Morphic primitivity – ; Fixed points – ; Billaud’ ; s Conjecture
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7410
• 期：1
• 页码：440-451
• 全文大小：216.8 KB
• 参考文献：1. Billaud, M.: A problem with words. Letter in Newsgroup Comp. Theory (1993), https://groups.google.com/d/topic/comp.theory/V_xDDtoR9a4/discussion
  2. Freydenberger, D.D., Nevisi, H., Reidenbach, D.: Weakly unambiguous morphisms. Theoretical Computer Science (to appear)
  3. Freydenberger, D.D., Reidenbach, D., Schneider, J.C.: Unambiguous morphic images of strings. International Journal of Foundations of Computer Science 17, 601–628 (2006)
  4. Head, T.: Fixed languages and the adult languages of 0L schemes. International Journal of Computer Mathematics 10, 103–107 (1981)
  5. Holub, S.: Polynomial-time algorithm for fixed points of nontrivial morphisms. Discrete Mathematics 309, 5069–5076 (2009)
  6. Lev茅, F., Richomme, G.: On a conjecture about finite fixed points of morphisms. Theoretical Computer Science 339, 103–128 (2005)
  7. Nevisi, H., Reidenbach, D.: Unambiguous 1-uniform morphisms. In: Proc. 8th International Conference on Words, WORDS 2011. EPTCS, vol. 63, pp. 158–167 (2011)
  8. Reidenbach, D., Schneider, J.C.: Morphically primitive words. Theoretical Computer Science 410, 2148–2161 (2009)
  9. Reidenbach, D., Schneider, J.C.: Restricted ambiguity of erasing morphisms. Theoretical Computer Science 412, 3510–3523 (2011)
  10. Schneider, J.C.: Unambiguous erasing morphisms in free monoids. RAIRO – Theoretical Informatics and Applications 44, 193–208 (2010)
• 作者单位：1. Department of Computer Science, Loughborough University, Loughborough, Leicestershire LE11 3TU, UK
• ISSN：1611-3349

文摘

An alphabet reduction is a 1-uniform morphism that maps a word to an image that contains a smaller number of different 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 different type of alphabet reduction, but is otherwise closely related to the main subject of our paper – and prove its correctness for a special case.