8
$\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.

Improve this question
$\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$
    – Qiaochu Yuan
    Commented 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$
    – Klaus Draeger
    Commented Jan 12, 2011 at 14:39
  • 2
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/…. $\endgroup$
    – Yuval Filmus
    Commented 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
    Commented 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$
    – Yuval Filmus
    Commented Jan 13, 2011 at 15:05

2 Answers 2

Reset to default
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..

Improve this answer
$\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$
    – Neel Krishnaswami
    Commented 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$
    – Łukasz Grabowski
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Dylan Thurston
    Commented 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$
    – Benjamin Steinberg
    Commented Jun 23, 2011 at 1:33
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .