# A special class of languages: “circular” languages. Is it known?

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

• 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 Jan 11 '11 at 17:54
• p.s maybe this is obvious, but why do you think that circular languages are a subclass of regular languages ? – Suresh Venkat Jan 11 '11 at 17:55
• @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 Jan 11 '11 at 18:27
• – Hsien-Chih Chang 張顯之 Jan 12 '11 at 9:08
• 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 Jan 14 '11 at 13:50

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.

• 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 Jan 12 '11 at 3:20
• "Since the only words not in the language have length $n^2$" Shouldn't that be $nm$? – Mark Reitblatt Jan 12 '11 at 3:21
• 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 Jan 12 '11 at 3:54
• 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 Jan 12 '11 at 4:01
• 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 Jan 12 '11 at 5:01

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.

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

• You are right. I've removed my incorrect post. – Dave Clarke Jan 11 '11 at 16:16
• 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 Jan 11 '11 at 21:19
• @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 Jan 11 '11 at 22:01
• 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 Jan 11 '11 at 23:09
• 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 Jan 12 '11 at 3:34

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

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.

• 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 Jan 13 '11 at 2:58
• 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 Jan 13 '11 at 3:25
• @Peter, have you read this answer? It was trying to prove that any circular language (without the condition of regularity) is regular. – Yuval Filmus Jan 13 '11 at 15:03
• @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 Jan 13 '11 at 15:11
• Yes, I use CIRCULARITY/TM to refer to this. CIRCULARITY/DFA is probably decidable. – chazisop Jan 16 '11 at 16:53