<p>Here are some papers that discuss these languages:</p>

<p>Thierry Cachat, The power of one-letter rational languages, DLT 2001, Springer LNCS #2295 (2002), 145-154.</p>

<p>S. Hovath, P. Leupold, and G. Lischke, Roots and powers of regular languages, DLT 2002, Springer LNCS #2450 (2003), 220-230.</p>

<p>H. Bordihn, Context-freeness of the power of context-free languages is undecidable, TCS 314 (2004), 445-449.</p>

CC BY-SA 2.5
2011-01-13T17:46:07.673Z
2011-01-13T17:46:07.673Z
Jeffrey Shallit
<p>@Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*.</p>

<p>In terms of decidability, a language $L$ is circular if there is an $L&#39;$ such that $L$ is the closure under + of $L&#39;$ or if it is a finite union of circular languages.</p>

<p>(I'm dying to redefine "circular" replacing your $&gt;$ with $\ge$. It simplifies things a lot. We can then characterise the circular languages as those for which there exists a NDFA whose starting state has only epsilon-transitions to accepting states and has an epsilon-transition to each accepting state).</p>

CC BY-SA 2.5
2011-01-11T16:16:58.460Z
You are right. I've removed my incorrect post.
Dave Clarke
CC BY-SA 2.5
2011-01-11T21:19:11.567Z
Regarding adaption with $\geq$: I am thinking that a minimal DFA should always have exactly one accepting state, namely the start state. Maybe more accepting states can happen, but then they need an $\varepsilon$-transition to the start state.
Raphael
CC BY-SA 2.5
2011-01-11T22:01:43.683Z
@Raphael, consider again L = a*|b*. A DFA whose start state is the only accepting state and which accepts a and b must accept (a|b)*.
Peter Taylor
CC BY-SA 2.5
2011-01-11T23:09:49.663Z
On the question of decidability, again: suppose you have a DFA with $n$ states of which $n_a$ are accepting. Suppose it accepts a word $w$, and also accepts $w^2$, $w^3$, ..., $w^{n_a+1}$. Then it accepts $w^x$ for $x > 0$. (Proof is a straightforward application of the pigeonhole principle).

If it's possible to show that the minimal (minimising $|w|$) counterexample ($w$, $x$) to the circularity of the language accepted by the DFA has length bounded by a function of $n$ then brute force testing is possible. I suspect that $|w| <= n+1$, but I haven't proved it.
Peter Taylor
CC BY-SA 2.5
2011-01-12T03:34:53.497Z
To follow up on @Raphael's idea above. The idea of start state = only accept state is wrong for this problem, but it does capture some interesting property. When M is a minDFA, the start state is the only accept state if and only if L(M) is the Kleene star of a prefix-free language. This is one of my favorite DFA trivia tidbits and thus I am quick to share it! ;)
mikero
CC BY-SA 2.5
2011-01-11T16:04:43.243Z
2011-01-11T18:24:48.690Z
2011-01-11T18:24:48.690Z
Peter Taylor
<p>Edit: A complete (simplified) PSPACE-completeness proof appears below.</p>

<p>Two updates. First, the normal form described in my other answer appears already in a paper by Calbrix and Nivat titled <em>Prefix and period languages of rational $\omega$-langauges</em>, unfortunately not available online.</p>

<p>Second, deciding whether a language is circular given its DFA is PSPACE-complete.</p>

<p><strong>Circularity in PSPACE.</strong> Since NPSPACE=PSPACE by Savitch's theorem, it is enough to give an NPSPACE algorithm for non-circularity. Let $A = (Q,\Sigma,\delta,q_0,F)$ be a DFA with $|Q|=n$ states. The fact that the syntactic monoid of $L(A)$ has size at most $n^n$ implies that if $L(A)$ is not circular then there is a word $w$ of length at most $n^n$ such that $w \in L(A)$ but $w^k \notin L(A)$ for some $k \leq n$. The algorithm guesses $w$ and computes $\delta_w(q) = \delta(q,w)$ for all $q \in Q$, using $O(n\log n)$ space (used to count up to $n^n$). It then verifies that $\delta_w(q_0) \in F$ but $\delta_w^{(k)} \notin F$ for some $k \leq n$.</p>

<p><strong>Circularity is PSPACE-hard.</strong> Kozen showed in his classic 1977 paper <a href="http://www.cs.cornell.edu/~kozen/papers/LowerBounds.pdf" rel="nofollow"><em>Lower bounds for natural proof systems</em></a> that it is PSPACE-hard to decide, given a list of DFAs, whether the intersection of the languages accepted by them is empty. We reduce this problem to circularity. Given binary DFAs $A_1,\ldots,A_n$, we find a prime $p \in [n,2n]$ and construct a ternary DFA $A$ accepting the language
$$ L(A) = \overline{\{2w_12w_2\cdots2w_p : w_i \in L(A_{1+(i\mod{n})})\}}. $$
(With some more effort, we can make $A$ binary as well.) It is not difficult to see (using the fact that $p$ is prime) that $L(A)$ is circular if and only if the intersection $L(A_1) \cap \cdots \cap L(A_n)$ is empty.</p>

CC BY-SA 3.0
2012-08-30T20:51:13.567Z
2012-09-03T02:40:20.310Z
2012-09-03T02:40:20.310Z
Yuval Filmus
<p>Every $s \in L$ of length $p&gt;0$ can be written as $xy^{i}z$ where $ x = z =  \epsilon $ , $ y = w \neq \epsilon$ . It's obvious that $|xy| \leq p $ and $ |y| = |w| &gt; 0 $. It follows that the language is regular for non-empty inputs, by the pumping lemma.</p>

<p>For $ w= \epsilon $ , the definition holds, since a NDFA that accepts the empty string will also accept any number of empty strings.</p>

<p>The union of the above languages is the language L and since regular languages are closed under union, it follows that every circular language is regular.</p>

<p>By Rice's theorem, $CIRCULARITY/TM$ is undecidable. The proof is similar to regularity.</p>

CC BY-SA 2.5
2011-01-13T02:58:30.543Z
The pumping lemma is a necessary, but not sufficient, condition for regularity. In particular, there are nonregular languages satisfying the pumping condition. Also, Rice's theorem would say that $\{\langle M\rangle\vert L(M)\text{ is circular}\}$ is undecidable. This does not mean that $\{\langle D\rangle\vert L(D)\text{ is circular}\}$ is undecidable (where $D$ is a DFA, $M$ a TM)! For instance, emptiness testing for DFAs is decidable, while emptiness testing for TMs is not.
alpoge
CC BY-SA 2.5
2011-01-13T03:25:34.833Z
Here's a non-computable circular language. Let $D = \{ 0^x 1 : x \in R\}$, where $R$ is some non-computable language (e.g. codes of halting TMs). Then $D^*$ is circular but clearly non-computable (an oracle for $D^*$ can be used to decide $R$).
Yuval Filmus
CC BY-SA 2.5
2011-01-13T07:31:14.633Z
@Yuval, D* isn't circular, AIUI the definition, because it's not regular.
Peter Taylor
CC BY-SA 2.5
2011-01-13T15:03:17.583Z
@Peter, have you read this answer? It was trying to prove that any circular language (without the condition of regularity) is regular.
Yuval Filmus
CC BY-SA 2.5
2011-01-13T15:11:40.040Z
@Yuval, my mistake.

@chazisop, the pumping lemma is useful for proving non-regularity of languages, but not regularity. (Besides, the assertion of your first sentence reduces to "Every $s \in L$ of length $p > 0$ can be written as $y^i$ where $y \ne \epsilon$", which is clearly false).
Peter Taylor
CC BY-SA 2.5
2011-01-13T15:58:15.560Z
Yes, I agree with you, the pumping lemma cannot prove regularity and I am going to edit the answer. Otherwise , the proof is correct, since every input of this language can be written as $w^{i}$ , with i>0 , by definition of circular languages.
chazisop
CC BY-SA 2.5
2011-01-16T16:53:16.267Z
Yes, I use CIRCULARITY/TM to refer to this. CIRCULARITY/DFA is probably decidable.
chazisop
CC BY-SA 2.5
2011-01-16T18:23:01.853Z
Ah, alright. Don't mind me, then!
alpoge
CC BY-SA 2.5
2011-01-13T02:26:45.880Z
2011-01-13T02:26:45.880Z
chazisop
<p>In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is a union of languages of the form $r^+$ (here $r$ could be the empty regexp); the union is not necessarily disjoint. In the fourth part, we exhibit a circular language which cannot be written as a disjoint sum $\sum r_i^+$.</p>

<p>Edit: Incorporated some corrections following Mark's comments. In particular, my earlier claims that circularity is coNP-complete or NP-hard are corrected.</p>

<p>Edit: Corrected normal form from $\sum r_i^*$ to $\sum r_i^+$. Exhibited an "inherently ambiguous" language.</p>

<hr>

<p>Continuing Peter Taylor's comment, here's how to decide (extremely inefficiently) whether a language is circular given its DFA. Construct a new DFA whose states are $n$-tuples of the old states. This new DFA runs $n$ copies of the old DFA in parallel.</p>

<p>If the language is not circular then there is a word $w$ such that if we run it through the DFA repeatedly, starting with the initial state $s_0$, then we get states $s_1,\ldots,s_n$ such that $s_1$ is accepting but one of the other ones is not accepting (if all of them are accepting then then the sequence $s_0,\ldots,s_n$ must cycle so that $w^*$ is always in the language). In other words, we have a path from $s_0,\ldots,s_{n-1}$ to $s_1,\ldots,s_n$ where $s_1$ is accepting but one of the others is not accepting. Conversely, if the language is circular then that cannot happen.</p>

<p>So we've reduced the problem to a simple directed reachability test (just check all possible "bad" $n$-tuples).</p>

<hr>

<p>The problem of circularity is coNP-hard. Suppose we're given a 3SAT instance with $n$ variables $\vec{x}$ and $m$ clauses $C_1,\ldots,C_m$. We can assume that $n = m$ (add dummy variables) and that $n$ is prime (otherwise find a prime between $n$ and $2n$ using AKS primality testing, and add dummy variables and clauses).</p>

<p>Consider the following language: "the input is <i>not</i> of the form $\vec{x}_1 \cdots \vec{x}_n$ where $\vec{x}_i$ is a satisfying assignment for $C_i$". It is easy to construct an $O(n^2)$ DFA for this language. If the language is not circular then there is a word $w$ in the language, some power of which is not in the language. Since the only words not in the language have length $n^2$, $w$ must be of length $1$ or $n$. If it is of length $1$, consider $w^n$ instead (it is still in the language), so that $w$ is in the language and $w^n$ is not in the language. The fact that $w^n$ is not in the language means that $w$ is a satisfying assignment.</p>

<p>Conversely, any satisfying assignment translates to a word proving the non-circularity of the language: the satisfying assignment $w$ belongs to the language but $w^n$ does not. Thus the language is circular iff the 3SAT instance is unsatisfiable.</p>

<hr>

<p>In this part, we discuss a normal form for circular languages. Consider some DFA for a circular language $L$. A sequence $C = C_0,\ldots$ is <i>real</i> if $C_0 = s$ (the initial state), all other states are accepting, and $C_i = C_j$ implies $C_{i+1} = C_{j+1}$. Thus every real sequence is eventually periodic, and there are only finitely many real sequences (since the DFA has finitely many states).</p>

<p>We say that a word <i>behaves according to $C$</i> if the word takes the DFA from state $c_i$ to state $c_{i+1}$, for all $i$. The set of all such words $E(C)$ is regular (the argument is similar to the first part of this answer). Note that $E(C)$ is a subset of $L$.</p>

<p>Given a real sequence $C$, define $C^k$ to be the sequence $C^k(t) = C(kt)$. The sequence $C^k$ is also real. Since there are only finitely many different sequences $C^k$, the language $D(C)$ which is the union of all $E(C^k)$ is also regular.</p>

<p>We claim that $D(C)$ has the property that if $x,y \in D(C)$ then $xy \in D(C)$. Indeed, suppose that $x \in C^k$ and $y \in C^l$. Then $xy \in C^{k+l}$. Thus $D(C) = D(C)^+$ can be written in the form $r^+$ for some regular expression $r$.</p>

<p>Every word $w$ in the language corresponds to some real sequence $C$, i.e. there exists a real sequence $C$ that $w$ behaves according to. Thus $L$ is the union of $D(C)$ over all real sequence $C$. Therefore every circular language has a representation of the form $\sum r_i^+$. Conversely, every such language is circular (trivially).</p>

<hr>

<p>Consider the circular language $L$ of all words over $a,b$ that contain either an even number or $a$'s or an even number of $b$'s (or both). We show that it cannot be written as a disjoint sum $\sum r_i^+$; by "disjoint" we mean that $r_i^+ \cap r_j^+ = \varnothing$.</p>

<p>Let $N_i$ be the size of the some DFA for $r_i^+$, and $N &gt; \max N_i$ be some <i>odd</i> integer. Consider $x = a^N b^{N!}$. Since $x \in L$, $x \in r_i^+$ for some $i$. By the pumping lemma, we can pump a prefix of $x$ of length at most $N$. Thus $r_i^+$ generates $z = a^{N!} b^{N!}$. Similarly, $y = a^{N!} b^N$ is generated by some $r_j^+$, which also generates $z$. Note that $i \neq j$ since $xy \notin L$. Thus the representation cannot be disjoint.</p>

CC BY-SA 2.5
2011-01-12T03:20:49.090Z
There seem to be a number of errors here. You're reducing from UNSAT, not SAT, so you're showing it's coNP-hard. What's your polynomial time witness for (non)-membership?
Mark Reitblatt
CC BY-SA 2.5
2011-01-12T03:21:24.673Z
"Since the only words not in the language have length $n^2$" Shouldn't that be $nm$?
Mark Reitblatt
CC BY-SA 2.5
2011-01-12T03:54:32.307Z
I don't think it's "trivially in coNP". At least, it's not trivially obvious to me. The "obvious" certificate would be a string $l$ in the language, and a power $k$ such that $l^k$ isn't in the language. But it's not immediately obvious to me why such a word must be polynomially-sized. Maybe it's by a simple fact of automata theory that I'm overlooking.
Mark Reitblatt
CC BY-SA 2.5
2011-01-12T04:01:07.760Z
An even more serious apparent flaw is that you jump from each clause being satisfiable individually to the whole formula being satisfiable. Unless I am misreading, of course.
Mark Reitblatt
CC BY-SA 2.5
2011-01-12T05:01:20.383Z
I agree that it's not clear that circularity is in coNP. On the other hand, I see no problems in the rest of the argument (now that I've put $n = m$). If each clause is satisfied by the same assignment, then the 3SAT instance is satisfied by this assignment.
Yuval Filmus
CC BY-SA 2.5
2011-01-12T16:08:48.067Z
@Yuval I misunderstood what you were doing. That part looks good now, except you're still showing coNP-hard rather than NP-hard.
Mark Reitblatt
CC BY-SA 2.5
2011-01-12T16:34:43.027Z
Yep, you're right again. It seemed that NP-hardness is the same as coNP-hardness but that's not the case for Karp reductions. I stand corrected.
Yuval Filmus
CC BY-SA 2.5
2011-01-12T02:40:15.397Z
2011-01-13T00:48:50.417Z
2011-01-13T00:48:50.417Z
Yuval Filmus
<p>Define the following class of "circular" languages over a finite alphabet Sigma. 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.</p>

<p>A language L is circular iff for all words $w$ in $\Sigma^*$, we have:</p>

<p>$w$ belongs to L if and only if for all integers $k &gt; 0$, $w^k$ belongs to L.</p>

<p>Is this class of languages known? I am interested in the circular languages which are also regular and in particular in:</p>

<ul>
<li><p>a name for them, if they are already known</p></li>
<li><p>decidability of the problem, given an automaton (in particular: a
DFA), whether the accepted language obeys to the above definition</p></li>
</ul>

CC BY-SA 4.0
2024-01-28T15:28:47.060Z
There's a notion of "cyclic language" studied here https://link.springer.com/chapter/10.1007/3-540-60922-9_5 which considers the requirement of this question plus the requirement of being closed under conjugation, with characterizations of the regular cyclic languages. (This is not the same notion as the circular languages studied in DNA computing.)
Antoine Amarilli 'a3nm'
CC BY-SA 2.5
2011-01-11T17:54:36.497Z
This is a very interesting question. Two related questions: 1) if we have a regular language L and an associated DFA, can we make it circular ? 2) Given any language L, is it the case that circ(L) is regular or has some nice properties ?
Suresh Venkat
CC BY-SA 2.5
2011-01-11T17:55:10.583Z
p.s maybe this is obvious, but why do you think that circular languages are a subclass of regular languages ?
Suresh Venkat
CC BY-SA 2.5
2011-01-11T18:27:12.760Z
@Suresh, I think he's defining a language to be circular iff it is a) regular; b) satisfies a closure property $\forall w \in L, n \in \mathbb{N} : w^n \in L$.
Peter Taylor
CC BY-SA 2.5
2011-01-12T09:08:58.623Z
[Crosspost in MO](http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known).
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-13T13:06:52.023Z
Yes, sorry for the confusion, I am interested in the regular and circular languages (in fact, only in those that do not contain the empty word). I also crossposted this to http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known - maybe it was inappropriate to do so. Reading the other comments.
vincenzoml
CC BY-SA 2.5
2011-01-14T13:50:19.540Z
Maybe thanks should not be posted, but this was my first question and I appreciated a lot the quality of the comments, answers, and discussion. Thanks.
vincenzoml
<fl.formal-languages><automata-theory><regular-language>
A special class of languages: “circular” languages. Is it known?
vincenzoml
# A special class of languages: “circular” languages. Is it known?

(Asked by: username_0 on 2011-01-11)

Define the following class of "circular" languages over a finite alphabet Sigma. 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 iff for all words $w$ in $\Sigma^\*$, we have:

$w$ belongs to L if and only if for all integers $k > 0$, $w^k$ belongs to L.

Is this class of languages known? I am interested in the circular languages which are also regular and in particular in:

* a name for them, if they are already known
* decidability of the problem, given an automaton (in particular: a
  DFA), whether the accepted language obeys to the above definition

**Tags:** fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_2**: This is a very interesting question. Two related questions: 1) if we have a regular language L and an associated DFA, can we make it circular ? 2) Given any language L, is it the case that circ(L) is regular or has some nice properties ?  
> **username_2**: p.s maybe this is obvious, but why do you think that circular languages are a subclass of regular languages ?  
> **username_3**: @Suresh, I think he's defining a language to be circular iff it is a) regular; b) satisfies a closure property $\forall w \in L, n \in \mathbb{N} : w^n \in L$.  
> **username_4**: [Crosspost in MO](http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known).  
> **username_0**: Yes, sorry for the confusion, I am interested in the regular and circular languages (in fact, only in those that do not contain the empty word). I also crossposted this to http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known - maybe it was inappropriate to do so. Reading the other comments.  
> **username_0**: Maybe thanks should not be posted, but this was my first question and I appreciated a lot the quality of the comments, answers, and discussion. Thanks.  
> **username_1**: There's a notion of "cyclic language" studied here https://link.springer.com/chapter/10.1007/3-540-60922-9_5 which considers the requirement of this question plus the requirement of being closed under conjugation, with characterizations of the regular cyclic languages. (This is not the same notion as the circular languages studied in DNA computing.)  

---

## 5 answers

### Answer by username_9 on 2011-01-12. Score: 19 | Accepted answer

In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is a union of languages of the form $r^+$ (here $r$ could be the empty regexp); the union is not necessarily disjoint. In the fourth part, we exhibit a circular language which cannot be written as a disjoint sum $\sum r\_i^+$.

Edit: Incorporated some corrections following Mark's comments. In particular, my earlier claims that circularity is coNP-complete or NP-hard are corrected.

Edit: Corrected normal form from $\sum r\_i^\*$ to $\sum r\_i^+$. Exhibited an "inherently ambiguous" language.

---

Continuing Peter Taylor's comment, here's how to decide (extremely inefficiently) whether a language is circular given its DFA. Construct a new DFA whose states are $n$-tuples of the old states. This new DFA runs $n$ copies of the old DFA in parallel.

If the language is not circular then there is a word $w$ such that if we run it through the DFA repeatedly, starting with the initial state $s\_0$, then we get states $s\_1,\ldots,s\_n$ such that $s\_1$ is accepting but one of the other ones is not accepting (if all of them are accepting then then the sequence $s\_0,\ldots,s\_n$ must cycle so that $w^\*$ is always in the language). In other words, we have a path from $s\_0,\ldots,s\_{n-1}$ to $s\_1,\ldots,s\_n$ where $s\_1$ is accepting but one of the others is not accepting. Conversely, if the language is circular then that cannot happen.

So we've reduced the problem to a simple directed reachability test (just check all possible "bad" $n$-tuples).

---

The problem of circularity is coNP-hard. Suppose we're given a 3SAT instance with $n$ variables $\vec{x}$ and $m$ clauses $C\_1,\ldots,C\_m$. We can assume that $n = m$ (add dummy variables) and that $n$ is prime (otherwise find a prime between $n$ and $2n$ using AKS primality testing, and add dummy variables and clauses).

Consider the following language: "the input is *not* of the form $\vec{x}\_1 \cdots \vec{x}\_n$ where $\vec{x}\_i$ is a satisfying assignment for $C\_i$". It is easy to construct an $O(n^2)$ DFA for this language. If the language is not circular then there is a word $w$ in the language, some power of which is not in the language. Since the only words not in the language have length $n^2$, $w$ must be of length $1$ or $n$. If it is of length $1$, consider $w^n$ instead (it is still in the language), so that $w$ is in the language and $w^n$ is not in the language. The fact that $w^n$ is not in the language means that $w$ is a satisfying assignment.

Conversely, any satisfying assignment translates to a word proving the non-circularity of the language: the satisfying assignment $w$ belongs to the language but $w^n$ does not. Thus the language is circular iff the 3SAT instance is unsatisfiable.

---

In this part, we discuss a normal form for circular languages. Consider some DFA for a circular language $L$. A sequence $C = C\_0,\ldots$ is *real* if $C\_0 = s$ (the initial state), all other states are accepting, and $C\_i = C\_j$ implies $C\_{i+1} = C\_{j+1}$. Thus every real sequence is eventually periodic, and there are only finitely many real sequences (since the DFA has finitely many states).

We say that a word *behaves according to $C$* if the word takes the DFA from state $c\_i$ to state $c\_{i+1}$, for all $i$. The set of all such words $E(C)$ is regular (the argument is similar to the first part of this answer). Note that $E(C)$ is a subset of $L$.

Given a real sequence $C$, define $C^k$ to be the sequence $C^k(t) = C(kt)$. The sequence $C^k$ is also real. Since there are only finitely many different sequences $C^k$, the language $D(C)$ which is the union of all $E(C^k)$ is also regular.

We claim that $D(C)$ has the property that if $x,y \in D(C)$ then $xy \in D(C)$. Indeed, suppose that $x \in C^k$ and $y \in C^l$. Then $xy \in C^{k+l}$. Thus $D(C) = D(C)^+$ can be written in the form $r^+$ for some regular expression $r$.

Every word $w$ in the language corresponds to some real sequence $C$, i.e. there exists a real sequence $C$ that $w$ behaves according to. Thus $L$ is the union of $D(C)$ over all real sequence $C$. Therefore every circular language has a representation of the form $\sum r\_i^+$. Conversely, every such language is circular (trivially).

---

Consider the circular language $L$ of all words over $a,b$ that contain either an even number or $a$'s or an even number of $b$'s (or both). We show that it cannot be written as a disjoint sum $\sum r\_i^+$; by "disjoint" we mean that $r\_i^+ \cap r\_j^+ = \varnothing$.

Let $N\_i$ be the size of the some DFA for $r\_i^+$, and $N > \max N\_i$ be some *odd* integer. Consider $x = a^N b^{N!}$. Since $x \in L$, $x \in r\_i^+$ for some $i$. By the pumping lemma, we can pump a prefix of $x$ of length at most $N$. Thus $r\_i^+$ generates $z = a^{N!} b^{N!}$. Similarly, $y = a^{N!} b^N$ is generated by some $r\_j^+$, which also generates $z$. Note that $i \neq j$ since $xy \notin L$. Thus the representation cannot be disjoint.

> **Comments:**
> **username_12**: There seem to be a number of errors here. You're reducing from UNSAT, not SAT, so you're showing it's coNP-hard. What's your polynomial time witness for (non)-membership?  
> **username_12**: "Since the only words not in the language have length $n^2$" Shouldn't that be $nm$?  
> **username_12**: I don't think it's "trivially in coNP". At least, it's not trivially obvious to me. The "obvious" certificate would be a string $l$ in the language, and a power $k$ such that $l^k$ isn't in the language. But it's not immediately obvious to me why such a word must be polynomially-sized. Maybe it's by a simple fact of automata theory that I'm overlooking.  
> **username_12**: An even more serious apparent flaw is that you jump from each clause being satisfiable individually to the whole formula being satisfiable. Unless I am misreading, of course.  
> **username_9**: I agree that it's not clear that circularity is in coNP. On the other hand, I see no problems in the rest of the argument (now that I've put $n = m$). If each clause is satisfied by the same assignment, then the 3SAT instance is satisfied by this assignment.  
> **username_12**: @Yuval I misunderstood what you were doing. That part looks good now, except you're still showing coNP-hard rather than NP-hard.  
> **username_9**: Yep, you're right again. It seemed that NP-hardness is the same as coNP-hardness but that's not the case for Karp reductions. I stand corrected.  

---

### Answer by username_5 on 2011-01-13. Score: 17

Here are some papers that discuss these languages:

Thierry Cachat, The power of one-letter rational languages, DLT 2001, Springer LNCS #2295 (2002), 145-154.

S. Hovath, P. Leupold, and G. Lischke, Roots and powers of regular languages, DLT 2002, Springer LNCS #2450 (2003), 220-230.

H. Bordihn, Context-freeness of the power of context-free languages is undecidable, TCS 314 (2004), 445-449.


---

### Answer by username_3 on 2011-01-11. Score: 6

@Dave Clarke, L = a\*|b\* would be circular, but L\* would be (a|b)\*.

In terms of decidability, a language $L$ is circular if there is an $L'$ such that $L$ is the closure under + of $L'$ or if it is a finite union of circular languages.

(I'm dying to redefine "circular" replacing your $>$ with $\ge$. It simplifies things a lot. We can then characterise the circular languages as those for which there exists a NDFA whose starting state has only epsilon-transitions to accepting states and has an epsilon-transition to each accepting state).

> **Comments:**
> **username_6**: You are right. I've removed my incorrect post.  
> **username_7**: Regarding adaption with $\geq$: I am thinking that a minimal DFA should always have exactly one accepting state, namely the start state. Maybe more accepting states can happen, but then they need an $\varepsilon$-transition to the start state.  
> **username_3**: @Raphael, consider again L = a*|b*. A DFA whose start state is the only accepting state and which accepts a and b must accept (a|b)*.  
> **username_3**: On the question of decidability, again: suppose you have a DFA with $n$ states of which $n_a$ are accepting. Suppose it accepts a word $w$, and also accepts $w^2$, $w^3$, ..., $w^{n_a+1}$. Then it accepts $w^x$ for $x > 0$. (Proof is a straightforward application of the pigeonhole principle).  If it's possible to show that the minimal (minimising $|w|$) counterexample ($w$, $x$) to the circularity of the language accepted by the DFA has length bounded by a function of $n$ then brute force testing is possible. I suspect that $|w| <= n+1$, but I haven't proved it.  
> **username_8**: To follow up on @Raphael's idea above. The idea of start state = only accept state is wrong for this problem, but it does capture some interesting property. When M is a minDFA, the start state is the only accept state if and only if L(M) is the Kleene star of a prefix-free language. This is one of my favorite DFA trivia tidbits and thus I am quick to share it! ;)  

---

### Answer by username_9 on 2012-08-30. Score: 5

Edit: A complete (simplified) PSPACE-completeness proof appears below.

Two updates. First, the normal form described in my other answer appears already in a paper by Calbrix and Nivat titled *Prefix and period languages of rational $\omega$-langauges*, unfortunately not available online.

Second, deciding whether a language is circular given its DFA is PSPACE-complete.

**Circularity in PSPACE.** Since NPSPACE=PSPACE by Savitch's theorem, it is enough to give an NPSPACE algorithm for non-circularity. Let $A = (Q,\Sigma,\delta,q\_0,F)$ be a DFA with $|Q|=n$ states. The fact that the syntactic monoid of $L(A)$ has size at most $n^n$ implies that if $L(A)$ is not circular then there is a word $w$ of length at most $n^n$ such that $w \in L(A)$ but $w^k \notin L(A)$ for some $k \leq n$. The algorithm guesses $w$ and computes $\delta\_w(q) = \delta(q,w)$ for all $q \in Q$, using $O(n\log n)$ space (used to count up to $n^n$). It then verifies that $\delta\_w(q\_0) \in F$ but $\delta\_w^{(k)} \notin F$ for some $k \leq n$.

**Circularity is PSPACE-hard.** Kozen showed in his classic 1977 paper [*Lower bounds for natural proof systems*](http://www.cs.cornell.edu/~kozen/papers/LowerBounds.pdf) that it is PSPACE-hard to decide, given a list of DFAs, whether the intersection of the languages accepted by them is empty. We reduce this problem to circularity. Given binary DFAs $A\_1,\ldots,A\_n$, we find a prime $p \in [n,2n]$ and construct a ternary DFA $A$ accepting the language
$$ L(A) = \overline{\{2w\_12w\_2\cdots2w\_p : w\_i \in L(A\_{1+(i\mod{n})})\}}. $$
(With some more effort, we can make $A$ binary as well.) It is not difficult to see (using the fact that $p$ is prime) that $L(A)$ is circular if and only if the intersection $L(A\_1) \cap \cdots \cap L(A\_n)$ is empty.


---

### Answer by username_10 on 2011-01-13. Score: 0

Every $s \in L$ of length $p>0$ can be written as $xy^{i}z$ where $ x = z = \epsilon $ , $ y = w \neq \epsilon$ . It's obvious that $|xy| \leq p $ and $ |y| = |w| > 0 $. It follows that the language is regular for non-empty inputs, by the pumping lemma.

For $ w= \epsilon $ , the definition holds, since a NDFA that accepts the empty string will also accept any number of empty strings.

The union of the above languages is the language L and since regular languages are closed under union, it follows that every circular language is regular.

By Rice's theorem, $CIRCULARITY/TM$ is undecidable. The proof is similar to regularity.

> **Comments:**
> **username_11**: The pumping lemma is a necessary, but not sufficient, condition for regularity. In particular, there are nonregular languages satisfying the pumping condition. Also, Rice's theorem would say that $\{\langle M\rangle\vert L(M)\text{ is circular}\}$ is undecidable. This does not mean that $\{\langle D\rangle\vert L(D)\text{ is circular}\}$ is undecidable (where $D$ is a DFA, $M$ a TM)! For instance, emptiness testing for DFAs is decidable, while emptiness testing for TMs is not.  
> **username_9**: Here's a non-computable circular language. Let $D = \{ 0^x 1 : x \in R\}$, where $R$ is some non-computable language (e.g. codes of halting TMs). Then $D^*$ is circular but clearly non-computable (an oracle for $D^*$ can be used to decide $R$).  
> **username_3**: @Yuval, D* isn't circular, AIUI the definition, because it's not regular.  
> **username_9**: @Peter, have you read this answer? It was trying to prove that any circular language (without the condition of regularity) is regular.  
> **username_3**: @Yuval, my mistake.  @chazisop, the pumping lemma is useful for proving non-regularity of languages, but not regularity. (Besides, the assertion of your first sentence reduces to "Every $s \in L$ of length $p > 0$ can be written as $y^i$ where $y \ne \epsilon$", which is clearly false).  
> **username_10**: Yes, I agree with you, the pumping lemma cannot prove regularity and I am going to edit the answer. Otherwise , the proof is correct, since every input of this language can be written as $w^{i}$ , with i>0 , by definition of circular languages.  
> **username_10**: Yes, I use CIRCULARITY/TM to refer to this. CIRCULARITY/DFA is probably decidable.  
> **username_11**: Ah, alright. Don't mind me, then!  

---

