Primitive words and roots of words

Details Primitive words and roots of words Primitive words and roots of words

2011-04-22

arxiv.org/abs/1104.4427v1

Acta Univ. Sapientiae, Informatica 3, 1 (2011) 5-34

Computer Science

Formal Languages and Automata Theory

Scientific paper

In the algebraic theory of codes and formal languages, the set $Q$ of all primitive words over some alphabet $\zi $ has received special interest. With this survey article we give an overview about relevant research to this topic during the last twenty years including own investigations and some new results. In Section 1 after recalling the most important notions from formal language theory we illustrate the connection between coding theory and primitive words by some facts. We define primitive words as words having only a trivial representation as the power of another word. Nonprimitive words (without the empty word) are exactly the periodic words. Every nonempty word is a power of an uniquely determined primitive word which is called the root of the former one. The set of all roots of nonempty words of a language is called the root of the language. The primitive words have interesting combinatorial properties which we consider in Section 2. In Section 3 we investigate the relationship between the set $Q$ of all primitive words over some fixed alphabet and the language classes of the Chomsky Hierarchy and the contextual languages over the same alphabet. The computational complexity of the set $Q$ and of the roots of languages are considered in Section 4. The set of all powers of the same degree of all words from a language is the power of this language. We examine the powers of languages for different sets of exponents, and especially their regularity and context-freeness, in Section 5, and the decidability of appropriate questions in Section 6. Section 7 is dedicated to several generalizations of the notions of periodicity and primitivity of words.

Affiliated with

Also associated with

No associations

Rating

Primitive words and roots of words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Primitive words and roots of words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Primitive words and roots of words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-330715