6
$\begingroup$

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.

$\endgroup$
5
  • 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$ Jan 11, 2011 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$ Jan 12, 2011 at 14:39
  • 2
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/…. $\endgroup$ Jan 12, 2011 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, 2011 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$ Jan 13, 2011 at 15:05

2 Answers 2

2
$\begingroup$

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..

$\endgroup$
7
  • 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$ Jan 12, 2011 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$ Jan 12, 2011 at 13:47
  • $\begingroup$ In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$. $\endgroup$ Jan 12, 2011 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$ Jan 12, 2011 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$ Jun 23, 2011 at 1:33
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ben, it looks like you gave twice the same link. $\endgroup$
    – J.-E. Pin
    Aug 6, 2013 at 16:02
  • $\begingroup$ Oops. I will have to hunt the correct one. $\endgroup$ Aug 6, 2013 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.