<p>We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end in the same state. C-automata can clearly only accept regular circular languages, since a rotation of a run is still a run (circularity), and a normal NFA can guess the existence of a run (regularity). Moreover, starting from any NFA <span class="math-container">$A$</span>, we can obtain a C-automaton for the circular closure of <span class="math-container">$L(A)$</span> (it is how we can prove the first item mentioned by @a3nm in the question), so the model is able to recognize any regular circular language, since such a language is its own circular closure.</p>
<p>This automaton model can in turn help to prove that the proposition of @MarzioDeBiasi for a MSO characterization is correct. Let us consider the logic <span class="math-container">$MSO[S']$</span>, where S' is the successor relation <span class="math-container">$(x,x+1)$</span> augmented with the pair <span class="math-container">$(last,first)$</span>. It is clear that this logic can only express regular circular languages, since <span class="math-container">$S'$</span> is invariant by rotation. Moreover, the fact that a C-automaton has an accepting run can be expressed in <span class="math-container">$MSO[S']$</span>: the formula can guess a labeling by states, and verify all the conditions asked in a run of a C-automaton. Notice that the condition that the first state <span class="math-container">$q_0$</span> is the same as the last will be verified in the same way as all other transitions, by verifying that there is a transition <span class="math-container">$(q_{n-1},a_n,q_0)$</span> on the last letter. In fact the formula cannot distinguish this case from the other transitions.</p>
<p>Remark that the equality <span class="math-container">$x=y$</span> can be expressed by <span class="math-container">$\exists t. S'(t,x)\wedge S'(t,y)$</span>, so we do not need to add it explicitly in the signature. This allows to express languages such as &quot;there is a unique occurrence of <span class="math-container">$a$</span>&quot;.</p>
<p>We can conclude that both C-automata and <span class="math-container">$MSO[S']$</span> characterize the class of regular circular languages.</p>

CC BY-SA 4.0
2024-02-02T09:31:02.003Z
Nice, it seems to work! A rephrase is a DFA in which the initial state is picked at random (among all states) and that state becomes the only final state.
Marzio De Biasi
CC BY-SA 4.0
2024-02-02T13:21:31.530Z
The random formulation is kind of a can of worms, it will give a probability that a word is accepted. What you want is more of an existential quantification, which is the same as setting all states initial.
Denis
CC BY-SA 4.0
2024-02-02T13:47:51.840Z
you're right, I was wondering if there is another way to get rid of the "all states initial" (another option is "an $\epsilon$ move to all states" but it doesn't add anything nor make your formulation simpler/more "elegant").
Marzio De Biasi
CC BY-SA 4.0
2024-03-05T10:09:52.547Z
I'm reacting very late to this, but thanks a lot @Denis for your answer, those are two very nice characterisations! :)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-02-01T23:20:46.243Z
2024-02-02T00:11:56.803Z
2024-02-02T00:11:56.803Z
Denis
<p>Just an extended note trying to recover my previous (wrong) answer.</p>
<p>A language <span class="math-container">$L$</span> is closed under cyclic shifts if and only if</p>
<p><span class="math-container">$aw \in L \Leftrightarrow wa \in L\;$</span> (<span class="math-container">$a \in \Sigma$</span>)</p>
<p>indeed after applying a single shift (<em>rotation</em>) you can apply the condition another time on the new string and so on.</p>
<p>As noted by Rémi in his comment the condition is equivalent to <span class="math-container">$xy \in L \Leftrightarrow yx \in L$</span>;<br />
so <em>cyclic shift = rotation = conjugation</em>.</p>
<p>In the MSO logic characterization of regular languages the above condition is equivalent to using the relation <span class="math-container">$succrot$</span> instead of the usual relation <span class="math-container">$&lt;$</span>; where <span class="math-container">$succrot$</span> can be defined (in MSO) as:</p>
<p><span class="math-container">$succrot(x,y)  \stackrel{\text{def}}{=}  succ(x, y) \lor (first(y) \land last(x)) $</span><br />
<span class="math-container">$= (x &lt; y \land \neg\exists z. x&lt;z&lt;y) \lor (\neg\exists z . (x &lt; z \lor z &lt; y) )$</span></p>
<p>(<em>still thinking if it's not too weak</em> :-)</p>

CC BY-SA 4.0
2024-01-31T09:59:01.397Z
In your logic you can define the language $ab^*a$ which is not circular, by saying that there are at least 2 $a$, and for any two distinct $a$ positions $x,y$ we have $x<y$.
Denis
CC BY-SA 4.0
2024-01-31T11:42:28.470Z
@Denis can you be more precise: in my language < doesn't exist and also "distinct" should be defined using $ <^s$. Do you see a way to define $ab^*a$ using $<^s$ instead of $<$?
Marzio De Biasi
CC BY-SA 4.0
2024-01-31T12:08:15.180Z
yes here is the formula:

$[\exists x,y. x<^s y \wedge a(x)\wedge a(y)]
\wedge [\forall x,y. a(x)\wedge a(y) \Rightarrow x=y\vee x<^s y]$.
The first part says that two $a$ exist, and the second says that the only $a$'s are at the first and last position.
Denis
CC BY-SA 4.0
2024-01-31T12:16:12.417Z
If you don't have $x=y$ in your signature, it is equivalent to $\neg (x<^s y \vee y<^s x)$. I'm ignoring here the words with less than 2 letters but the counter-example stands regardless of the behaviour on these words.
Denis
CC BY-SA 4.0
2024-01-31T12:30:55.630Z
(btw I forgot the "s" superscript in my very first  answer, sorry it would have been much clearer with $x<^s y$ which is what I meant)
Denis
CC BY-SA 4.0
2024-01-31T13:24:00.323Z
@Denis: you're right. I'll see if it can be fixed with an "elegant" relation. The informal condition to capture is: $\varphi \to \varphi'$ where $\varphi'$ is obtained from $\varphi$ replacing each $x$ with $y$ and adding the condition $succmod(x,y)$ defined as $y=x+1 \lor (first(y) \land last(x))$
Marzio De Biasi
CC BY-SA 4.0
2024-02-01T12:31:54.073Z
@Denis perhaps using a logic restricted only  to the $succrot$ relation should work: $x<^{succrot}y = [(x < y) \land \lnot \exists z . x<z<y] \lor [ (first(y) \land last(x)]$ .   if it is not too weak
Marzio De Biasi
CC BY-SA 4.0
2024-02-01T20:48:03.377Z
it looks plausible. to prove that it's the case it would probably help to have an equivalent automaton model, but this does not look obvious. I was thinking about unfolding the word into a bi-infinite word labeled by $\mathbb Z$ and using usual automata model on this, but this loses information about the length.
Denis
CC BY-SA 4.0
2024-02-01T21:51:27.347Z
maybe the corresponding automaton model is quite simple as well: no initial or final state, but there must be a transition from the last position to the first, and an accepting transition somewhere.
Denis
CC BY-SA 4.0
2024-01-29T08:55:44.910Z
2024-02-01T14:01:45.387Z
2024-02-01T14:01:45.387Z
Marzio De Biasi
<p>A language <span class="math-container">$L$</span> is <em>closed under circular shifts</em> if, for every word <span class="math-container">$w = a_1 ... a_n$</span> and <a href="https://en.wikipedia.org/wiki/Circular_shift" rel="noreferrer">circular shift</a> <span class="math-container">$w' = a_i ... a_n a_1 ... a_{i-1}$</span> of <span class="math-container">$w$</span>, then <span class="math-container">$w \in L$</span> iff <span class="math-container">$w' \in L$</span>. It is equivalent to require that <span class="math-container">$L$</span> is <em>closed under conjugation</em>, i.e., for every word <span class="math-container">$w = uv$</span>, letting <span class="math-container">$w' = vu$</span>, we have <span class="math-container">$w \in L$</span> iff <span class="math-container">$w' \in L$</span>.</p>
<p>These closure requirements are weaker that requiring the language to be <em>closed under permutation</em> or <em>commutative</em>, i.e., for any word <span class="math-container">$w = a_1 ... a_n$</span>, for every permutation <span class="math-container">$\sigma$</span> of <span class="math-container">$\{1, ..., n\}$</span>, letting <span class="math-container">$w' = a_{\sigma(1)} ... a_{\sigma(n)}$</span>, we have <span class="math-container">$w \in L$</span> iff <span class="math-container">$w' \in L$</span>.</p>
<p><strong>Is there a simple characterization of the regular languages that are closed under cyclic shifts?</strong> I'm thinking about a characterization that would make such languages easy to understand. For instance, the commutative regular languages can be easily understood: membership to the language is determined by the <a href="https://en.wikipedia.org/wiki/Parikh%27s_theorem" rel="noreferrer">Parikh image</a>, and then being regular means the language only imposes a threshold or modularity condition on the components of the Parikh image.</p>
<p>Some related work:</p>
<ul>
<li>It is known that the closure of a regular language under cyclic shifts is also regular, and the same is also known of context-free languages. There is a study of the state complexity of the operation of closing under cyclic shift <a href="https://www.cambridge.org/core/journals/rairo-theoretical-informatics-and-applications/article/abs/state-complexity-of-cyclic-shift/BA456D52176EB7390475DCA2E28D6FCD" rel="noreferrer">here</a> but it doesn't characterize the languages that are already closed.</li>
<li>There is a notion of <em>cyclic language</em> that has been studied, e.g., <a href="https://link.springer.com/chapter/10.1007/3-540-60922-9_5" rel="noreferrer">here</a>. A cyclic language is closed under conjugation and also satisfies requirement that for every word <span class="math-container">$w$</span> and power <span class="math-container">$n$</span> we have <span class="math-container">$w \in L$</span> iff <span class="math-container">$w^n \in L$</span>, i.e., membership to the language is determined by the primitive root of words. (This requirement is discussed in <a href="https://cstheory.stackexchange.com/questions/4254/a-special-class-of-languages-circular-languages-is-it-known">this question</a>.) There is also a notion of <em>strongly cyclic language</em> in this paper which is defined in terms of automata but do not seem to be the class I ask about.</li>
<li>There is a related notion of <em>circular languages</em> studied in bioinformatics (e.g., <a href="https://www.sciencedirect.com/science/article/pii/S030439751000294X" rel="noreferrer">here</a>) where words are quotiented to see them as circular, but I'm not sure of the relationship.</li>
</ul>

CC BY-SA 4.0
2024-01-29T16:50:24.643Z
Have you looked towards equations for lattices of languages (in the sense of §XII.1 of https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf—see also §XIII.5 for the difference with classical profinite equations)? This approach seems to work at least for the cyclic languages you mentioned, see §XIV.1.5.
*A priori* languages closed under cyclic shifts should be exactly those satisfying $xy \leftrightarrow yx$.
Rémi
CC BY-SA 4.0
2024-03-05T10:16:55.197Z
@Rémi I see; nice indeed that Prop 1.21 in XII.1 distinguishes both parts of the definitions of the cyclic languages. I must confess I haven't looked for now at what these equations mean, but thanks for the pointer!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-03-07T16:13:15.050Z
The characterization can be reformulated as follows: a language L is cyclic iff, letting $S(L)$ be the syntactic semigroup of $L$ and $\textrm{Acc}$ be the subset of $S(L)$ accepting $L$, for all $x,y \in S(L)$, $xy \in \textrm{Acc} \Leftrightarrow yx \in \textrm{Acc}$. But I'm not entirely convinced that this qualifies as "easy to understand" for most (reasonable) people.
Rémi
CC BY-SA 4.0
2024-03-08T10:50:11.217Z
@Rémi: ah, once rephrased like this, I think the characterization is pretty easy to understand, I would even say it's almost "too easy" -- superficially, it sounds like the immediate translation of being closed under circular shifts, seen on the syntactic monoid rather than on words. But this is still nice to know, so thanks!
Antoine Amarilli 'a3nm'
<fl.formal-languages><regular-language><permutations>
Is there a simple characterization of regular languages closed under circular shifts?
Antoine Amarilli 'a3nm'
# Is there a simple characterization of regular languages closed under circular shifts?

(Asked by: username_0 on 2024-01-28)

A language $L$ is *closed under circular shifts* if, for every word $w = a\_1 ... a\_n$ and [circular shift](https://en.wikipedia.org/wiki/Circular_shift) $w' = a\_i ... a\_n a\_1 ... a\_{i-1}$ of $w$, then $w \in L$ iff $w' \in L$. It is equivalent to require that $L$ is *closed under conjugation*, i.e., for every word $w = uv$, letting $w' = vu$, we have $w \in L$ iff $w' \in L$.

These closure requirements are weaker that requiring the language to be *closed under permutation* or *commutative*, i.e., for any word $w = a\_1 ... a\_n$, for every permutation $\sigma$ of $\{1, ..., n\}$, letting $w' = a\_{\sigma(1)} ... a\_{\sigma(n)}$, we have $w \in L$ iff $w' \in L$.

**Is there a simple characterization of the regular languages that are closed under cyclic shifts?** I'm thinking about a characterization that would make such languages easy to understand. For instance, the commutative regular languages can be easily understood: membership to the language is determined by the [Parikh image](https://en.wikipedia.org/wiki/Parikh%27s_theorem), and then being regular means the language only imposes a threshold or modularity condition on the components of the Parikh image.

Some related work:

* It is known that the closure of a regular language under cyclic shifts is also regular, and the same is also known of context-free languages. There is a study of the state complexity of the operation of closing under cyclic shift [here](https://www.cambridge.org/core/journals/rairo-theoretical-informatics-and-applications/article/abs/state-complexity-of-cyclic-shift/BA456D52176EB7390475DCA2E28D6FCD) but it doesn't characterize the languages that are already closed.
* There is a notion of *cyclic language* that has been studied, e.g., [here](https://link.springer.com/chapter/10.1007/3-540-60922-9_5). A cyclic language is closed under conjugation and also satisfies requirement that for every word $w$ and power $n$ we have $w \in L$ iff $w^n \in L$, i.e., membership to the language is determined by the primitive root of words. (This requirement is discussed in [this question](https://cstheory.stackexchange.com/questions/4254/a-special-class-of-languages-circular-languages-is-it-known).) There is also a notion of *strongly cyclic language* in this paper which is defined in terms of automata but do not seem to be the class I ask about.
* There is a related notion of *circular languages* studied in bioinformatics (e.g., [here](https://www.sciencedirect.com/science/article/pii/S030439751000294X)) where words are quotiented to see them as circular, but I'm not sure of the relationship.

**Tags:** fl.formal-languages, regular-language, permutations
> **Comments:**
> **username_1**: Have you looked towards equations for lattices of languages (in the sense of §XII.1 of https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf—see also §XIII.5 for the difference with classical profinite equations)? This approach seems to work at least for the cyclic languages you mentioned, see §XIV.1.5. *A priori* languages closed under cyclic shifts should be exactly those satisfying $xy \leftrightarrow yx$.  
> **username_0**: @Rémi I see; nice indeed that Prop 1.21 in XII.1 distinguishes both parts of the definitions of the cyclic languages. I must confess I haven't looked for now at what these equations mean, but thanks for the pointer!  
> **username_1**: The characterization can be reformulated as follows: a language L is cyclic iff, letting $S(L)$ be the syntactic semigroup of $L$ and $\textrm{Acc}$ be the subset of $S(L)$ accepting $L$, for all $x,y \in S(L)$, $xy \in \textrm{Acc} \Leftrightarrow yx \in \textrm{Acc}$. But I'm not entirely convinced that this qualifies as "easy to understand" for most (reasonable) people.  
> **username_0**: @Rémi: ah, once rephrased like this, I think the characterization is pretty easy to understand, I would even say it's almost "too easy" -- superficially, it sounds like the immediate translation of being closed under circular shifts, seen on the syntactic monoid rather than on words. But this is still nice to know, so thanks!  

---

## 2 answers

### Answer by username_2 on 2024-02-01. Score: 6 | Accepted answer

We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end in the same state. C-automata can clearly only accept regular circular languages, since a rotation of a run is still a run (circularity), and a normal NFA can guess the existence of a run (regularity). Moreover, starting from any NFA $A$, we can obtain a C-automaton for the circular closure of $L(A)$ (it is how we can prove the first item mentioned by @a3nm in the question), so the model is able to recognize any regular circular language, since such a language is its own circular closure.

This automaton model can in turn help to prove that the proposition of @MarzioDeBiasi for a MSO characterization is correct. Let us consider the logic $MSO[S']$, where S' is the successor relation $(x,x+1)$ augmented with the pair $(last,first)$. It is clear that this logic can only express regular circular languages, since $S'$ is invariant by rotation. Moreover, the fact that a C-automaton has an accepting run can be expressed in $MSO[S']$: the formula can guess a labeling by states, and verify all the conditions asked in a run of a C-automaton. Notice that the condition that the first state $q\_0$ is the same as the last will be verified in the same way as all other transitions, by verifying that there is a transition $(q\_{n-1},a\_n,q\_0)$ on the last letter. In fact the formula cannot distinguish this case from the other transitions.

Remark that the equality $x=y$ can be expressed by $\exists t. S'(t,x)\wedge S'(t,y)$, so we do not need to add it explicitly in the signature. This allows to express languages such as "there is a unique occurrence of $a$".

We can conclude that both C-automata and $MSO[S']$ characterize the class of regular circular languages.

> **Comments:**
> **username_3**: Nice, it seems to work! A rephrase is a DFA in which the initial state is picked at random (among all states) and that state becomes the only final state.  
> **username_2**: The random formulation is kind of a can of worms, it will give a probability that a word is accepted. What you want is more of an existential quantification, which is the same as setting all states initial.  
> **username_3**: you're right, I was wondering if there is another way to get rid of the "all states initial" (another option is "an $\epsilon$ move to all states" but it doesn't add anything nor make your formulation simpler/more "elegant").  
> **username_0**: I'm reacting very late to this, but thanks a lot @Denis for your answer, those are two very nice characterisations! :)  

---

### Answer by username_3 on 2024-01-29. Score: 2

Just an extended note trying to recover my previous (wrong) answer.

A language $L$ is closed under cyclic shifts if and only if

$aw \in L \Leftrightarrow wa \in L\;$ ($a \in \Sigma$)

indeed after applying a single shift (*rotation*) you can apply the condition another time on the new string and so on.

As noted by Rémi in his comment the condition is equivalent to $xy \in L \Leftrightarrow yx \in L$;  
so *cyclic shift = rotation = conjugation*.

In the MSO logic characterization of regular languages the above condition is equivalent to using the relation $succrot$ instead of the usual relation $<$; where $succrot$ can be defined (in MSO) as:

$succrot(x,y) \stackrel{\text{def}}{=} succ(x, y) \lor (first(y) \land last(x)) $  
$= (x < y \land \neg\exists z. x

(*still thinking if it's not too weak* :-)

> **Comments:**
> **username_2**: In your logic you can define the language $ab^*a$ which is not circular, by saying that there are at least 2 $a$, and for any two distinct $a$ positions $x,y$ we have $x<y$.  
> **username_3**: @Denis can you be more precise: in my language < doesn't exist and also "distinct" should be defined using $ <^s$. Do you see a way to define $ab^*a$ using $<^s$ instead of $<$?  
> **username_2**: yes here is the formula:  $[\exists x,y. x<^s y \wedge a(x)\wedge a(y)] \wedge [\forall x,y. a(x)\wedge a(y) \Rightarrow x=y\vee x<^s y]$. The first part says that two $a$ exist, and the second says that the only $a$'s are at the first and last position.  
> **username_2**: If you don't have $x=y$ in your signature, it is equivalent to $\neg (x<^s y \vee y<^s x)$. I'm ignoring here the words with less than 2 letters but the counter-example stands regardless of the behaviour on these words.  
> **username_2**: (btw I forgot the "s" superscript in my very first  answer, sorry it would have been much clearer with $x<^s y$ which is what I meant)  
> **username_3**: @Denis: you're right. I'll see if it can be fixed with an "elegant" relation. The informal condition to capture is: $\varphi \to \varphi'$ where $\varphi'$ is obtained from $\varphi$ replacing each $x$ with $y$ and adding the condition $succmod(x,y)$ defined as $y=x+1 \lor (first(y) \land last(x))$  
> **username_3**: @Denis perhaps using a logic restricted only  to the $succrot$ relation should work: $x<^{succrot}y = [(x < y) \land \lnot \exists z . x<z<y] \lor [ (first(y) \land last(x)]$ .   if it is not too weak  
> **username_2**: it looks plausible. to prove that it's the case it would probably help to have an equivalent automaton model, but this does not look obvious. I was thinking about unfolding the word into a bi-infinite word labeled by $\mathbb Z$ and using usual automata model on this, but this loses information about the length.  
> **username_2**: maybe the corresponding automaton model is quite simple as well: no initial or final state, but there must be a transition from the last position to the first, and an accepting transition somewhere.  

---

