Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Domaratzki, Michael; Rampersad, Narad (2010)
Languages: English
Types: Conference object
Subjects: : Mathematics [Physical, chemical, mathematical & earth Sciences], Computer Science - Formal Languages and Automata Theory, : Mathématiques [Physique, chimie, mathématiques & sciences de la terre]

Classified by OpenAIRE into

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
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [11] J. Gabarro´ . Some applications of the interchange lemma. Bull. EATCS, 25:19-21, 1985.
    • [12] G. Hardy and E. Wright. An Introduction to the Theory of Numbers. Oxford Science Publications, 5th edition, 2000.
    • [13] J. Je¸drzejowicz and A. Szepietowski. On the expressive power of the shuffle operator matched with intersection by regular sets. Theoretical Informatics and Applications, 35:379-388, 2001.
    • [14] M. Lothaire. Combinatorics on words. Cambridge University Press, 1997.
    • [15] H. Petersen. The ambiguity of primitive words. In P. Enjalbert, E. Mayr, and K. Wagner, editors, STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings, volume 775 of Lecture Notes in Computer Science, pages 679-690, 1994.
    • [16] L. B. Richmond and J. Shallit. Counting Abelian squares. Elec. J. Combinatorics, 16:R72, 2009.
    • [17] G. Rozenberg and A. Salomaa. Handbook of Formal Languages, volume 1. Springer, 1997.
    • [18] H. Shyr. Free Monoids and Languages. Hon Min Book Company, 3rd edition, 2001.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article