20
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ 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 ? $\endgroup$ Jan 11, 2011 at 17:54
  • $\begingroup$ p.s maybe this is obvious, but why do you think that circular languages are a subclass of regular languages ? $\endgroup$ Jan 11, 2011 at 17:55
  • 3
    $\begingroup$ @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$. $\endgroup$ Jan 11, 2011 at 18:27
  • $\begingroup$ Crosspost in MO. $\endgroup$ Jan 12, 2011 at 9:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – vincenzoml
    Jan 14, 2011 at 13:50

5 Answers 5

19
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Jan 12, 2011 at 3:20
  • $\begingroup$ "Since the only words not in the language have length $n^2$" Shouldn't that be $nm$? $\endgroup$ Jan 12, 2011 at 3:21
  • $\begingroup$ 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. $\endgroup$ Jan 12, 2011 at 3:54
  • $\begingroup$ 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. $\endgroup$ Jan 12, 2011 at 4:01
  • $\begingroup$ 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. $\endgroup$ Jan 12, 2011 at 5:01
17
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ You are right. I've removed my incorrect post. $\endgroup$ Jan 11, 2011 at 16:16
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Jan 11, 2011 at 21:19
  • 1
    $\begingroup$ @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)*. $\endgroup$ Jan 11, 2011 at 22:01
  • $\begingroup$ 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. $\endgroup$ Jan 11, 2011 at 23:09
  • $\begingroup$ 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! ;) $\endgroup$
    – mikero
    Jan 12, 2011 at 3:34
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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