Abelian Primitive Words

Conference object, Preprint English OPEN
Domaratzki, Michael ; Rampersad, Narad (2010)
  • Subject: : Mathematics [Physical, chemical, mathematical & earth Sciences] | Computer Science - Formal Languages and Automata Theory | : Mathématiques [Physique, chimie, mathématiques & sciences de la terre]
    acm: TheoryofComputation_GENERAL | ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Computer Science::Formal Languages and Automata Theory

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes. Peer reviewed
  • References (18)
    18 references, page 1 of 2

    [1] I. Anderson. On primitive sequences. Journal London Math. Soc, 42:137-148, 1967.

    [2] I. Anderson. Combinatorics of finite sets. Dover Publications, 2002.

    [3] E. Bach and J. Shallit. Algorithmic Number Theory, volume 1. MIT Press, 1997.

    [4] J. Berstel and L. Boasson. The set of Lyndon words is not context-free. Bull. EATCS, 63:139-140, 1997.

    [5] S. Constantinescu and L. Ilie. Fine and Wilf's theorem for Abelian periods. Bull. EATCS, 89:167-170, 2006.

    [6] R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective. Springer, 2nd edition, 2005.

    [7] E. Czeizler, L. Kari, and S. Seki. On a special class of primitive words. Theoretical Computer Science, 411:617- 630, 2010.

    [8] N. de Bruijn, C. van Ebbenhorst Tengbergen, and D. Kruyswijk. On the set of divisors of a number. Nieuw Arch. Wiskunde, 23:191-193, 1951.

    [9] M. Domaratzki. Trajectory-Based Operations. PhD thesis, Queen's University, 2004.

    [10] P. Do¨ mo¨ si, S. Horva´th, M. Ito, L Ka´szonyi, and M. Katsura. Formal languages consisting of primitive words. In Z. E´ sik, editor, Fundamentals of Computation Theory, 9th International Symposium, FCT '93, Szeged, Hungary, August 23-27, 1993, Proceedings, volume 710 of Lecture Notes in Computer Science, pages 194-203. Springer, 1993.

  • Metrics
    No metrics available
Share - Bookmark