11
$\begingroup$

A language $L$ is closed under circular shifts if, for every word $w = a_1 ... a_n$ and 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, 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 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. 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.) 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) where words are quotiented to see them as circular, but I'm not sure of the relationship.
$\endgroup$
4
  • 1
    $\begingroup$ Have you looked towards equations for lattices of languages (in the sense of §XII.1 of 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$. $\endgroup$
    – Rémi
    Jan 29 at 16:50
  • $\begingroup$ @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! $\endgroup$
    – a3nm
    Mar 5 at 10:16
  • $\begingroup$ 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. $\endgroup$
    – Rémi
    Mar 7 at 16:13
  • 1
    $\begingroup$ @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! $\endgroup$
    – a3nm
    Mar 8 at 10:50

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Feb 2 at 9:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – Denis
    Feb 2 at 13:21
  • $\begingroup$ 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"). $\endgroup$ Feb 2 at 13:47
  • $\begingroup$ I'm reacting very late to this, but thanks a lot @Denis for your answer, those are two very nice characterisations! :) $\endgroup$
    – a3nm
    Mar 5 at 10:09
2
$\begingroup$

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<z<y) \lor (\neg\exists z . (x < z \lor z < y) )$

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

$\endgroup$
9
  • $\begingroup$ 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$. $\endgroup$
    – Denis
    Jan 31 at 9:59
  • $\begingroup$ @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 $<$? $\endgroup$ Jan 31 at 11:42
  • $\begingroup$ 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. $\endgroup$
    – Denis
    Jan 31 at 12:08
  • $\begingroup$ 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. $\endgroup$
    – Denis
    Jan 31 at 12:16
  • $\begingroup$ (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) $\endgroup$
    – Denis
    Jan 31 at 12:30

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.