Peter, you are right.

From your proposition, we can define exactly the primitive words as follow.

Let us call CP(x) the set of all cyclic permutations of x.

Then the primitive words over an alphabet E, PW(E), will be the set of words x built from E such that the cardinal of CP(x) is equal to the length of x.

E.g

"abc" gives CP(abc) = { bca, cab, abc } (thus |CP(abc)| = 3 = |abc| ) and therefore abc is primitive

whereas

"abab" gives CP(abab)={ baba, abab } and by definition is not primitive

More formally (we exclude the zero length words):

PW( E) = { x in E* such that |x| > |CP(x)| > 0 }

Hope this could help at some point !

I shall think. This question seems interesting.

This might contain an answer to your question:

http://www.worldscientific.com/worldscibooks/10.1142/7265

My naïve intuition: I can imagine extending a CFG producing mirror recursion (e.g."[011…][…110]") with a set of non-CFG rules producing also a cross-serial dependency on the relevant segment (e.g. "[011…][110…][…011] ").

The pattern [X][X][X_mirror] is a primitive pattern, according to your definition, and it is out of the power of any CFG.

Hi Cristiano! The book is in good part about my question and all the ways in which people have tried to answer it. Although the book is not yet out, I have read drafts. But thank you for the reference anyway.

[X][X][X_mirror] will indeed be primitive in most cases unless X is a palindrome. But the problem is not finding a non-CF mechanism to produce primitive words, but to show that a CF mechanism cannot produce ALL of them. Indeed, every CF but not linear language contains infinitely primitive words; this is a result of mine. But this does not help to show that the language of all and only the primitive words is CF...

Interesting question... Seems to me that this is related to the problem of having a formal definition of those primitive words which would not be a negation (with such a formal definition, one can start reasoning with the help of a stronger frame). As a starting point, could we conceive a constructive definition of those words ?

Frankly, I do not understand what you mean by the negation of a word. Over a binary alphabet would it be the complement (0->1 and 1->0)? Or are you talking about a different type of negation?

A paper proposes a CFG (under Chomsky Normal Form) with four nonterminals generating only primitive words over three nonterminal symbols.

They used a computer program to study all cases...

Their approach is organized around this observation: " a grammar which generates all primitive words over an (at least two letter) alphabet and does not generate any non-primitive word can not contain the start symbol on the right hand side of any rule."

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1366-8.pdf

To Peter: sorry, I was not clear enough: I was talking about the definition of a primitive word (its is negative, since it says that there are *not* ...)

Okay, thank you J.-Y. So you would like a constructive definition. I do not really know any. Only for some subclasses like the ones in the article you mention. Another one that comes to my mind is the following: if a word u is a power of another word v, then the multiplicities of letters in u are multiples of those in v. If the multiplicities differ by one, then the word is necessarily primitive. Of course, this is only a subclass.

Or: a word is primitive iff all of its cyclic permutations (put the first letter to the end, next letter etc) are different. Because for a non-primitive vv after moving the letters of the first v we already arrive at the same word again.

Peter, I like the second one very much... it means, if I understand, the we could characterize primitive words as being the set of words stable under cyclic permutation. Now, it would be interesting to observe how cyclic permutations do impact the structure of CFG... in order to gain some intuitions about the initial problem (that's not the easy part I guess ;-) ; Perhaps a kind of inductive argument on the length of sentences ?

Well, not THE set stable under cyclic permutations. Of course, the set of all words is stable, also the set of all words with exactly two "b" etc. But the primitive words form A set stable under cyclic permutation, yes.

A related (very short) article is

http://www-igm.univ-mlv.fr/~berstel/Articles/1997-LyndonBEATCS.pdf

Context-free languages are closed under cyclic permutation. But, of course, the closure has a very different grammar in general. If one could show a restrictive characterization for all CF languages that are stable under cyclic permutation, it might be easier to show that primitive words do not fulfill this condition rather than the general CF definition.

Peter, you are right.

From your proposition, we can define exactly the primitive words as follow.

Let us call CP(x) the set of all cyclic permutations of x.

Then the primitive words over an alphabet E, PW(E), will be the set of words x built from E such that the cardinal of CP(x) is equal to the length of x.

E.g

"abc" gives CP(abc) = { bca, cab, abc } (thus |CP(abc)| = 3 = |abc| ) and therefore abc is primitive

whereas

"abab" gives CP(abab)={ baba, abab } and by definition is not primitive

More formally (we exclude the zero length words):

PW( E) = { x in E* such that |x| > |CP(x)| > 0 }

Hope this could help at some point !

Oups, sorry for the typo ( "=" instead of "

J.-Y. Vion-Dury,

Thanks a lot for your precise and wise elaboration on the carryying sense of primitive words. It seems to me that therapists who are in touch with persons after some brain damge(e.g. stroke ) could say a lot about the sense-carrying primitive utterances of their patients devoided of the ability to speak. Anyway, those people speak and their close relatives or therapists are able to understand them somehow and probably nobody has proven so far how it happens that this "disabled" speach is understandable.

Context in the very narrow and special sense of the definition of generative grammars in Formal Language Theory.

A book entitled *Context-Free Languages And Primitive Words*,

by Domosi, Horvath, and Ito, is supposedly about to appear.

A more approachable first focus might be the set of words

that are neither squares (ww) nor cubes (www). (Separately,

both the nonsquares and the noncubes *are* both context-free

and co-context-free.)

Or can you show that the number of states for a PDA that

recognizes k-th powers has to grow with k?

Peter: Your observation is correct, and indeed this (somewhat loose) relation to the prime numbers is one of the reasons, why most people believe that the language of primitive words is not context-free. As you say, the density function

d_L(n)=number of words of length n in language L

has some kind of peaks at the prime numbers.

However, nobody has been able to formalize this relation in a way that allows drawing this conclusion.

Joel: the idea with squares and cubes could be interesting. I think I have seen those results somewhere. Such a result would be a very strong indicator that the language is not context-free, even if it could not be generalized to all powers.

Well, your example is not correct. Indeed all words from (ab)* \cup (ab)*a with prime length are primitive. But the reverse is not true, indeed those words are primitive iff they are of UNEVEN length. ababababa of length nine is primitive.

I say "loose" connection in contrast to something like: "for prime length all words are primitive, for non-prime length all words are non-primitive" Instead of this we only have "for prime length all words are primitive, for non-prime length some but not all words are primitive". So there is no evident mapping or similar thing between the two sets.

The set of prime numbers (e.g. in the form {a^p: p is prime}) is non-context-free, even though it might be possible to test membership in polynomial time. The pumping lemma can be used to show this.

If you are familiar with the Pumping (Bar-Hillel)-Lemma, the non-context-freeness of primes in the form given above is straight-forward. If some a^p is in the language (i.e. p is prime) then there would have to exist a k such that for all i the words a^(p+ ik) are in the language, too. But these numbers are not all primes.

I am sorry, but I have to insist that primitive and in (AB)(AB)*A only implies that the length is odd, not that it is prime. Like in the example for length nine. The only possible divisors are one and three, but

ABA.BAB.ABA

is not a repetition of three times the same factor. One does not work either, so the word is primitive.

Looking at the grammar can indeed indicate something about the lengths of words. But it does not give us a count of the words of a given length, because one word might be derived in several ways. For unambiguous context-free languages we know from Holger Petersen that they do not contain the language of all primitive words. But there are context-free languages for which no unambiguous grammar exists.

Unfortunately I am right - otherwise the question could be solved via intersection with that regular language and the pumping argument. But then someone would have already done it...