Ins-Robust Primitive Words

Preprint English OPEN
Srivastava, Amit Kumar; Kapoor, Kalpesh;
(2017)
  • Subject: Mathematics - Combinatorics | Computer Science - Formal Languages and Automata Theory
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Computer Science::Formal Languages and Automata Theory

Let Q be the set of primitive words over a finite alphabet with at least two symbols. We characterize a class of primitive words, Q_I, referred to as ins-robust primitive words, which remain primitive on insertion of any letter from the alphabet and present some propert... View more
  • References (14)
    14 references, page 1 of 2

    [1] Pa´l Do¨ mo¨ si and Ge´za Horva´th. The language of primitive words is not regular: two simple proofs. Bulletin of European Association for Theoretical Computer Science, 87:191-194, 2005.

    [2] Pa´l Do¨ mo¨ si, Sa´ndor Horva´th, Masami Ito, La´szlo´ Ka´szonyi, and Masashi Katsura. Formal languages consisting of primitive words. In Fundamentals of Computation Theory, pages 194-203. Springer, 1993.

    [4] John E Hopcroft. Introduction to automata theory, languages, and computation. Pearson Education India, 1979.

    [5] Roman Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, pages 596-604. IEEE, 1999.

    [6] Roman Kolpakov and Gregory Kucherov. On maximal repetitions in words. In Fundamentals of Computation Theory, pages 374-385. Springer, 1999.

    [7] Wang Lijun. Count of primitive words. Applied Mathematics-A Journal of Chinese Universities, 16(3):339-344, 2001.

    [8] Gerhard Lischke. Primitive words and roots of words. arXiv preprint arXiv:1104.4427, 2011.

    [9] M Lothaire. Combinatorics on words. Cambridge University Press, 1997.

    [10] M Lothaire. Applied combinatorics on words, volume 105. Cambridge University Press, 2005.

    [11] Masami Ito Pa´l Do¨ mo¨ si. Primitive Words in Languages, chapter 9, pages 267-308. World Scientific, 2014.

  • Metrics
Share - Bookmark