Some Results on Primitive Words, Square-Free Words, and Disjunctive Languages

Tetsuo MORIYA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.10   pp.2514-2516
Publication Date: 2008/10/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.10.2514
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automata and Formal Language Theory
Keyword: 
primitive word,  square-free word,  principal congruence,  disjunctive language,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, we give some resuts on primitive words, square-free words and disjunctive languages. We show that for a word u ∈Σ+, every element of λ(cp(u)) is d-primitive iff it is square-free, where cp(u) is the set of all cyclic-permutations of u, and λ(cp(u)) is the set of all primitive roots of it. Next we show that pmqn is a primitive word for every n, m ≥1 and primitive words p, q, under the condition that |p| = |q| and (m, n) ≠ (1, 1). We also give a condition of disjunctiveness for a language.