Finite variation and idempotent languages and automata

Question

Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^*$ define the variation of $w$ w.r.t. $L$ by

$$\mathrm{Var}_L(w) := \#\{0\leq k < n \text{ s.t. } \delta(w_1\cdots w_k)\neq \delta(w_1\cdots w_{k+1})\},$$ if $w:=w_1\cdots w_n$.

We say $L$ is of finite variation if $\sup_{w\in\Sigma^*}\{\text{Var}_L(w)\}<+\infty$.

This should be equivalent to ask that the only cycles of $A$ are of length one (i.e., self-loops).

Now what else can be said about the class $\text{FV}$ of regular languages with finite variation? Is there a characterization in terms of regular expressions? Is there a characterization in terms of generating elements (under boolean operations)?

I can prove that $\text{FV}$ is a $*$-variety of Eilenberg, i.e. it is closed under boolean operations, left and right word quotients and inverse homomorphisms. By Eilenberg variety theorem there is an associated pseudovariety of monoids $M(\text{FV})$. Is there anything in the literature about $\text{FV}$ and $M(\text{FV})$?

What if we consider the literally idempotent closure of $\text{FV}$?

Much more important: is any of this questions non-trivial to experts? :-)

Answer 1

It seems to me that FV should be the variety of languages associated to $\mathcal R$-trivial monoids. A monoid is $\mathcal R$-trivial if Green's relation $\mathcal R$ is trivial. This is the same as satisfying $(xy)^{\omega}x=(xy)^{\omega}$ for all $x,y$ where $z^{\omega}$ is the idempotent power of $z$.

Suppose first that the language has finite variation. Then as you observed each oriented cycle must visit one vertex. In particular if $n$ is such that $(xy)^{\omega}=(xy)^n$, then there is a cycle at $q(xy)^n$ labeled by $(xy)^n$ for any state $q$. It follows that $x,y$ label loops at $q(xy)^n$ and so $q(xy)^nx=q(xy)^n$. Since $q$ was arbitrary, it follows $(xy)^nx=(xy)^n$

Conversely, the variety of $\mathcal R$-trivial languages is generated by languages of the form $A_1^*a_1A_2^*\cdots a_{n-1}A_n^*$ where the $A_i$ are subsets of the alphabet and $a_i\notin A_i$. The minimal automaton has $n$ states. The elements of $A_i$ label loops at state $i$ and $a_i$ goes from state $i$ to $i+1$. Clearly this language has finite variation.

More conceptual argument (update): Let me rephrase the above proof to make it self-contained. Recall a monoid $M$ is $\mathcal R$-trivial if $aM=bM$ implies $a=b$.

Proposition. Let $L$ be a regular language. The following are equivalent.

1. $L$ has finite variation.
2. Each strong connected component of the minimal automaton of $L$ has a single vertex.
3. There is a total ordering on the states of the minimal automaton of $L$ such that $qa\geq q$ for all states $q$ and inputs $a$.
4. The syntactic monoid of $L$ is $\mathcal R$-trivial.

Proof:
(1) iff (2). If there is a nontrivial strongly connected component, then there is an oriented cycle $p$ visiting at least 2 vertices and with no repeated vertices. If $w$ is the label of $p$, then the words $w^n$ show that the variation is not finite. If all strongly connected components are trivial then the variation is bounded by the length of the longest loop edge-free path.

(2) implies (3). Removing the loop edges gives an acyclic digraph. Topologically sort the states. Then by construction (3) holds since loop edges fix you and all other transitions go up in the order.

(3) implies (4) This is well known and can be found in Pin's book. The functions satisfying $qf\geq q$ for all states $q$ form a submonoid. Suppose $u,v$ generate the same right ideal of the syntactic monoid, the $u=vx$ and $v=uy$ for some $x,y$. Thus for any state $q$ we have $qu=qvx\geq qv=quy\geq qu$. Thus $u=v$.

(4) implies (2). Suppose that $q,q'$ are in the same strongly connected component. There are elements of the syntactic monoid such that $qu=q'$ and $q'v=q$. Then $q(uv)^n=q$ and $q(uv)^nu=q'$ for all $n$. Choose $n$ so that $(uv)^n$ is idempotent. Then $(uv)^n$ generates the same right ideal as $(uv)^nu$ and so they are equal. Thus $q=q'$. QED

Answer 2

It could also be of interest to notice that the condition on strongly connected component (or equivalently order on states), which says that all cycles are self-loops, when applied to alternating automata instead of nondeterministic ones, yields the variety of star-free (equivalently first-order, aperiodic) languages. See for instance V. Diekert and P. Gastin. First-order definable languages

Answer 3

As for my question on literally idempotent closure of $\mathrm{FV}=\mathrm{R}$ I can now answer by myself, thanks to Benjamin Steinberg.

By literally idempotent closure $\overline{V}$ of a $*$-variety of languages $V$ we mean the class $\overline{V}:=\{\overline{L} | L \in \mathrm{V}\}$, provided $\overline{L}:=\{w\in\Sigma^* \,|\, w\sim v \text{ for some } v\in L\}$, where $\sim$ is the synctatic congruence $\sim_L$ of $L$ enriched by relations $a^2 \sim a$ for all $a\in\Sigma$.

It has been proved by Klíma&Polák in [1] that for the variety $\mathrm{R}$ (and also for other varieties of general interest) one has $\mathrm{R}\cap \mathrm{Id}=\overline{\mathrm{R}}$ where $\mathrm{Id}$ is the $*$-literal-variety of literally idempotent regular languages (i.e. languages $L$ such that for every $x,y\in\Sigma^*$ one has $xa^2y\in L \iff xay\in L$).

Hence, using the characterization of Klíma&Polák in [1] we conclude that finite variation literally idempotent languages are exactly finite unions of languages of the following form:

$B_0^*a_1B_1^*a_2\ldots a_kB_k^*, k\in\mathbb{N}_0, a_1,\ldots,a_k\in \Sigma, B_i\subseteq \Sigma, a_1\neq a_2\neq \cdots \neq a_k$ and $B_0\not\ni a_1\in B_1\not\ni a_2\in B_2\cdots B_{k-1}\not\ni a_k\in B_k$.

Bibliography: [1] Ondřej Klíma, Libor Polák: On Varieties of Literally Idempotent Languages. ITA 42(3): 583–598 (2008)