# A special class of regular languages: “circular” languages. Is it known?

We can define a subclass of the regular languages. Fix an alphabet $\Sigma$. Define the "circular" languages (actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, that's a different class of languages).

A language $L$ is circular if and only if for all words $w \in \Sigma$, we have:

$w\in L$ if and only if, for all integers $k > 0$ we have $w^k\in L$.

Is this class of languages known? I am interested in:

• a name for it

• decidability of the problem, given an automaton (in particular: a DFA), whether the accepted language obeys to the above definition

• a "nice" characterization (e.g. equational?) of the definition.

-
There is a related notion of a cyclic language: they are closed under conjugation and powers. See crm.umontreal.ca/Words07/pdf/musikerslides.pdf . –  Qiaochu Yuan Jan 11 '11 at 15:29
Just to clarify: You are really only interested in languages which satisfy the cyclicity condition and are, in addition, regular? I ask because the condition itself does not imply regularity - consider, for example, the language of well-matched parentheses. –  Klaus Draeger Jan 12 '11 at 14:39
Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/…. –  Yuval Filmus Jan 12 '11 at 16:35
Yes I am interested in the regular languages that satisfy the condition I spelled. In fact I am only interested in languages that don't contain the empty word, but that's a separate condition. Sorry for the crosspost, I did not know what was the most appropriate place for the question. Maybe following up just on cstheory is better. A language is not circular if L=M* (and L=M+ does not fix this) as Lukasz Grabowski points out with his example. Yuval Filmus: is what you say that obvious? How do you identify the generators (your "r"). –  vincenzoml Jan 13 '11 at 13:04
@vincenzoml: See my answer on cstheory, part 3. As you mention, the correct normal form is a union of $r^+$'s, which unfortunately in general cannot be disjoint. –  Yuval Filmus Jan 13 '11 at 15:05

For deciding whether a language is "circular", you can just take the normalized DFA for the language (where the states correspond to sets of possible different completions). In that normalized DFA, a language is circular iff the only accept state is the start state, pretty much by definition.

I don't know what you want by a characterization. A language L has this property iff it is M* for some other language M, but that's not useful..

-
The automata construction you suggest always admits the empty string, but he required that $w^k \in L$ for $k > 0$, not $k \geq 0$. So $a+$ would be circular according to his definition, but its minimal automaton would not share accept and start states. –  Neel Krishnaswami Jan 12 '11 at 9:36
Dylan: Are you sure L is circular iff L=M*? The example I have in mind is a langauge on letters <a,b> consisting only of powers of a and of powers of b. AFAIU it is circular, but I can't see why it's M* for some M. –  Łukasz Grabowski Jan 12 '11 at 13:47
In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$. –  Yuval Filmus Jan 12 '11 at 16:37
Sorry, I was indeed premature. I'll try to fix this later. The right characterization should be using r+ rather than r*. –  Dylan Thurston Jan 12 '11 at 20:40
@Yuval, he asks that $w$ belongs to $L$ iff $w^k\in L$ for all positive $k$. Thus the language of all even powers of the letter $a$ is not circular in his sense although it is $(a^2)^*$. –  Benjamin Steinberg Jun 23 '11 at 1:33

Yuval Filmus shows in http://www.springerlink.com/content/gv6we2tjpua1puf5/ that it is decidable for a regular language $L$ whether $w\in L\implies w^k\in L$ for all $k>0$. I would guess there must be an older reference. On the other hand, a language $L$ is called pure if $w^k\in L\implies w\in L$. It was shown by Pedro Silva that purity is decidable for regular languages in http://cmup.fc.up.pt/cmup/preprints/2002-18.pdf

Since the notion of circular language in the question is the conjunction of these two properties, it is decidable if a regular language is circular.

-
Ben, it looks like you gave twice the same link. –  J.-E. Pin Aug 6 '13 at 16:02
Oops. I will have to hunt the correct one. –  Benjamin Steinberg Aug 6 '13 at 20:05