# 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 . Jan 11, 2011 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. Jan 12, 2011 at 14:39
• Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/…. Jan 12, 2011 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"). Jan 13, 2011 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. Jan 13, 2011 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. Jan 12, 2011 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. Jan 12, 2011 at 13:47
• In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$. Jan 12, 2011 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*. Jan 12, 2011 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)^*$. Jun 23, 2011 at 1:33

Yuval Filmus shows in Link 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. Aug 6, 2013 at 16:02
• Oops. I will have to hunt the correct one. Aug 6, 2013 at 20:05