Languages whose Parikh image is recognizable

Question

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By Parikh's theorem, every context-free language is a slip-language. But not every slip-language is context-free. For example, the commutative closure of $(abc)^*$ is not context-free.

In $\mathbb N_0^k$ with $k = |\Sigma|$, the semilinear set are precisely the rational sets. The recognizable set in $\mathbb N_0^k$ are finite unions of sets of the form $R_1 \times \ldots \times R_k$, with each $R_i$, for $i \in \{1,\ldots, k\}$, either finite or ultimately periodic.

The slip languages are an established concept. For example, we have work from the 70's, and such neat results as that the commutative closure of binary slip languages is context-free.

Now I am just curious. Is there anything known, or is there any research, on languages whose Parikh image is recognizable?

As recognizability is preserved under inverse homomorphism, the commutative closure of such a language is regular. But, there exist non-regular languages whose Parikh image is recognizable. For example, the language given by the context-free grammar $A \to aBaA | \varepsilon, B \to bAbB |\varepsilon$. It has the commutative closure $$ \{ w \in \{a,b\}^* \mid |w|_{a} \equiv 0 \pmod{2}, |w|_b \equiv 0 \pmod{2}, |w|_a \ge \min\{1, |w|_b\}. \}, $$ where $|w|_a$ and $|w|_b$ denote the number of $a$'s, respectively $b$'s, in $w$.

EDIT (8 May 2020): There was an error in the specification of the context-free grammar. I corrected it. Also I will give the proofs, just to be on the safe side. Let $L$ be the language generated by the grammar. Suppose it where regular with pumping constant $N$. Consider $w = (ab)^N(ba)^N \in L$, and let $v$ be some pumpable factor in $(ab)^N$. As any word in $L$ must have even length, this factor itself must have even length. Hence it starts with different symbols. So, we either have $w = (ab)^x(ab)^y(ab)^z(ba)^N$ with $N = x+y+z$ and $v = (ab)^y$, or $w = (ab)^xa(ba)^yb(ab)^z(ba)^N$ with $N - 1 = x+y+z$ and $v = (ba)^y$. But in either case, none of the pumped up strings would be in $L$, as they still only contain $bb$ as a factor with two consecutive equal symbols. But if the factor $bb$ (or $aa$) only appears once in a given word from $L$, it must have the form $(ab)^k(ba)^k$ or $(ab)^{k-1}aa(ab)^{k-1}$ for some $k > 0$. Alternatively, we could note that an infinite accepting automaton is given by the state set $\{1,2,3,\ldots\}$, with the letter $a$ interchanging $1$ and $2$, $3$ and $4$, and so on, and $b$ interchanging $2$ and $3$, $4$ and $5$ and so. As this is a permutation automaton with the single final state $\{1\}$, it is minimal. Finally, as $(aa)^{n-1}a(bb)^ma \in L$ for each $m \ge 0$, $n > 0$, and $(aa)^m \in L$ for each $m \ge 0$, and every word in $L$ has an even number of $a$'s and $b$'s, the claim about the commutative closure is implied.

EDIT (14 July 2021): The claim about the "infinite" permutation automaton made in the previous EDIT-block is wrong. I overlooked that we need a transition labelled with $b$ at the state $1$ too. Adding, for example, a self-loop would change the language (but still, nonetheless, gives an example of a non-regular language having regular commutative closure).

Answer 1

I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular.

Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular. Then, $p^{-1}(p(L)) \cap a_1^* \cdots a_k^*$ is regular, bounded and has the same Parikh image as $L$ or its commutative closure. By an old result of Ginsburg (see below), we can write this language as a finite union of languages of the form $A_1 \cdots A_k$, where each $A_i$ is a regular subset of $a_i^*$. Now, the Parikh image of one such set has the form $R_1 \times \ldots \times R_k$ with $R_i \subseteq \mathbb N$ recognizable. So, by a condition written in the question, the Parikh image of $L$ is recognizable.

Alternatively, without citing other results, suppose we have a morphism $h : \Sigma^* \to M$ with $M$ finite such that $p^{-1}(p(L)) = h^{-1}(h(L))$. We can assume $M$ is commutative (for example, by taking the syntactic monoid). Hence, the map $\varphi : \mathbb N_0^k \to M$ given by $\varphi(n_1, \ldots, n_k) = h(a_1)^{n_1} \cdots h(a_k)^{n_k}$ is a morphism. Then, $p(L) = \varphi^{-1}(h(L))$ and so $p(L)$ is recognizable.

Now, identifying language classes whose commutative closure is regular is quite an active field of research. For example, see the second reference below.

S. Ginsburg, Bounded Regular Sets, Amer. Math. Soc. 17 (1966), 1043-1049.

Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin: Regular languages and partial commutations. Inf. Comput. 230: 76-96 (2013)