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.

  • 2
    $\begingroup$ There is a related notion of a cyclic language: they are closed under conjugation and powers. See crm.umontreal.ca/Words07/pdf/musikerslides.pdf . $\endgroup$ – Qiaochu Yuan Jan 11 '11 at 15:29
  • $\begingroup$ 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. $\endgroup$ – Klaus Draeger Jan 12 '11 at 14:39
  • 2
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/…. $\endgroup$ – Yuval Filmus Jan 12 '11 at 16:35
  • $\begingroup$ 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"). $\endgroup$ – vincenzoml Jan 13 '11 at 13:04
  • $\begingroup$ @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. $\endgroup$ – 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..

  • 1
    $\begingroup$ 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. $\endgroup$ – Neel Krishnaswami Jan 12 '11 at 9:36
  • 2
    $\begingroup$ 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. $\endgroup$ – Łukasz Grabowski Jan 12 '11 at 13:47
  • $\begingroup$ In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$. $\endgroup$ – Yuval Filmus Jan 12 '11 at 16:37
  • $\begingroup$ Sorry, I was indeed premature. I'll try to fix this later. The right characterization should be using r+ rather than r*. $\endgroup$ – Dylan Thurston Jan 12 '11 at 20:40
  • $\begingroup$ @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)^*$. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.