<p>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.</p>
<p>Let <span class="math-container">$\Sigma = \{a_1, \ldots, a_k\}$</span>. One implication is given in the question. For the other, suppose the commutative closure of <span class="math-container">$L \subseteq \Sigma^*$</span> is regular, i.e., the set <span class="math-container">$p^{-1}(p(L))$</span> is regular.
Then,  <span class="math-container">$p^{-1}(p(L)) \cap a_1^* \cdots a_k^*$</span> is regular, bounded and has the same Parikh image as <span class="math-container">$L$</span> 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 <span class="math-container">$A_1 \cdots A_k$</span>, where each <span class="math-container">$A_i$</span> is a regular subset of <span class="math-container">$a_i^*$</span>. Now, the Parikh image of one such set has the form <span class="math-container">$R_1 \times \ldots \times R_k$</span> with <span class="math-container">$R_i \subseteq \mathbb N$</span> recognizable. So, by a condition written in the question, the Parikh image of <span class="math-container">$L$</span> is recognizable.</p>
<p>Alternatively, without citing other results, suppose we have a morphism <span class="math-container">$h : \Sigma^* \to M$</span> with <span class="math-container">$M$</span> finite such that <span class="math-container">$p^{-1}(p(L)) = h^{-1}(h(L))$</span>. We can assume <span class="math-container">$M$</span> is commutative (for example, by taking the syntactic monoid).
Hence, the map <span class="math-container">$\varphi : \mathbb N_0^k \to M$</span> given by <span class="math-container">$\varphi(n_1, \ldots, n_k) = h(a_1)^{n_1} \cdots h(a_k)^{n_k}$</span> is a morphism.
Then, <span class="math-container">$p(L) = \varphi^{-1}(h(L))$</span> and so <span class="math-container">$p(L)$</span> is recognizable.</p>
<p>Now, identifying language classes whose commutative closure is regular is quite an active field of research. For example, see the second reference below.</p>
<p>S. Ginsburg, <a href="https://www.ams.org/journals/proc/1966-017-05/S0002-9939-1966-0201310-3/S0002-9939-1966-0201310-3.pdf" rel="nofollow noreferrer">Bounded Regular Sets</a>, Amer. Math. Soc. 17 (1966), 1043-1049.</p>
<p>Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin:
<a href="https://www.sciencedirect.com/science/article/pii/S0890540113000771?via%3Dihub" rel="nofollow noreferrer">Regular languages and partial commutations</a>. Inf. Comput. 230: 76-96 (2013)</p>

CC BY-SA 4.0
2021-02-21T21:49:52.640Z
2021-02-21T21:49:52.640Z
StefanH
<p>Let <span class="math-container">$\Sigma$</span> be some alphabet, and <span class="math-container">$p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$</span> the <a href="https://en.wikipedia.org/wiki/Parikh%27s_theorem#Definitions_and_formal_statement" rel="nofollow noreferrer">Parikh map</a>. A formal language <span class="math-container">$L \subseteq \Sigma^*$</span> is called a <em>slip</em>-language, if <span class="math-container">$p(L)$</span> is a <a href="https://en.wikipedia.org/wiki/Generalized_arithmetic_progression#Semilinear_sets" rel="nofollow noreferrer">semilinear set</a>. By <a href="https://en.wikipedia.org/wiki/Parikh%27s_theorem" rel="nofollow noreferrer">Parikh's theorem</a>, every context-free language is a slip-language. But not every slip-language is context-free. For example, the commutative closure of <span class="math-container">$(abc)^*$</span> is not context-free.</p>
<p>In <span class="math-container">$\mathbb N_0^k$</span> with <span class="math-container">$k = |\Sigma|$</span>, the semilinear set are precisely the <a href="https://en.wikipedia.org/wiki/Rational_set" rel="nofollow noreferrer">rational sets</a>. The <a href="https://en.wikipedia.org/wiki/Recognizable_set" rel="nofollow noreferrer">recognizable set</a> in <span class="math-container">$\mathbb N_0^k$</span> are finite unions of sets of the form <span class="math-container">$R_1 \times \ldots \times R_k$</span>, with each <span class="math-container">$R_i$</span>, for <span class="math-container">$i \in \{1,\ldots, k\}$</span>, either finite or ultimately periodic.</p>
<p>The slip languages are an established concept. For example, we have <a href="https://www.sciencedirect.com/science/article/pii/S0022000071800247" rel="nofollow noreferrer">work from the 70's</a>, and such neat results as that the commutative closure of binary slip languages is <a href="https://www.sciencedirect.com/science/article/pii/S0166218X03003354" rel="nofollow noreferrer">context-free</a>.</p>
<p>Now I am just curious. Is there anything known, or is there any research, on languages whose Parikh image is recognizable?</p>
<p>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 <span class="math-container">$A \to aBaA | \varepsilon, B \to bAbB |\varepsilon$</span>. It has the commutative closure
<span class="math-container">$$
 \{ w \in \{a,b\}^* \mid |w|_{a} \equiv 0 \pmod{2}, |w|_b \equiv 0 \pmod{2},
 |w|_a \ge \min\{1, |w|_b\}. \},
$$</span>
where <span class="math-container">$|w|_a$</span> and <span class="math-container">$|w|_b$</span> denote the number of <span class="math-container">$a$</span>'s, respectively <span class="math-container">$b$</span>'s, in <span class="math-container">$w$</span>.</p>
<p>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 <span class="math-container">$L$</span> be the language generated by the grammar. Suppose it where regular with pumping constant <span class="math-container">$N$</span>. Consider <span class="math-container">$w = (ab)^N(ba)^N \in L$</span>, and let <span class="math-container">$v$</span> be some pumpable factor in <span class="math-container">$(ab)^N$</span>. As any word in <span class="math-container">$L$</span> must have even length, this factor itself must have even length. Hence it starts with different symbols. So, we either have <span class="math-container">$w = (ab)^x(ab)^y(ab)^z(ba)^N$</span> with <span class="math-container">$N = x+y+z$</span> and <span class="math-container">$v = (ab)^y$</span>, or <span class="math-container">$w = (ab)^xa(ba)^yb(ab)^z(ba)^N$</span> with <span class="math-container">$N - 1 = x+y+z$</span> and <span class="math-container">$v = (ba)^y$</span>. But in either case, none of the pumped up strings would be in <span class="math-container">$L$</span>, as they still only contain <span class="math-container">$bb$</span> as a factor with two consecutive equal symbols. But if the factor <span class="math-container">$bb$</span> (or <span class="math-container">$aa$</span>) only appears once in a given word from <span class="math-container">$L$</span>, it must have the form <span class="math-container">$(ab)^k(ba)^k$</span> or <span class="math-container">$(ab)^{k-1}aa(ab)^{k-1}$</span> for some <span class="math-container">$k &gt; 0$</span>. Alternatively, we could note that an infinite accepting automaton is given by the state set <span class="math-container">$\{1,2,3,\ldots\}$</span>, with the letter <span class="math-container">$a$</span> interchanging <span class="math-container">$1$</span> and <span class="math-container">$2$</span>, <span class="math-container">$3$</span> and <span class="math-container">$4$</span>, and so on, and <span class="math-container">$b$</span> interchanging <span class="math-container">$2$</span> and <span class="math-container">$3$</span>, <span class="math-container">$4$</span> and <span class="math-container">$5$</span> and so. As this is a permutation automaton with the single final state <span class="math-container">$\{1\}$</span>, it is minimal.
Finally, as <span class="math-container">$(aa)^{n-1}a(bb)^ma \in L$</span> for each <span class="math-container">$m \ge 0$</span>, <span class="math-container">$n &gt; 0$</span>, and <span class="math-container">$(aa)^m \in L$</span> for each <span class="math-container">$m \ge 0$</span>, and every word in <span class="math-container">$L$</span> has an even number of <span class="math-container">$a$</span>'s and <span class="math-container">$b$</span>'s, the claim about the commutative closure is implied.</p>
<p>EDIT (14 July 2021): The claim about the &quot;infinite&quot; permutation automaton made in the previous EDIT-block is wrong. I overlooked that we need a transition labelled with <span class="math-container">$b$</span> at the state <span class="math-container">$1$</span> 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).</p>

CC BY-SA 4.0
2020-05-06T20:27:41.633Z
I'm not sure if it will give you a clear answer, but a lot of the concepts you mention arise often when studying VASS (vector addition systems with states). Perhaps some of the results there will shed light on this.
Shaull
CC BY-SA 4.0
2020-05-06T20:47:25.033Z
@Shaull Thanks. At least it gives me a direction to look for :) Btw, if you know some specific resources/surveys about VASS, feel free to share them!
StefanH
CC BY-SA 4.0
2020-05-07T06:41:37.733Z
VASSs are mentioned often in https://cel.archives-ouvertes.fr/cel-00727025v2
Radu GRIGore
CC BY-SA 4.0
2020-05-07T18:22:50.303Z
I vaguely remember the concept of Parikh automata, as discussed here. http://cds.cern.ch/record/1321204?ln=en However, I cannot tell how well that automaton model fits with your question.
Hermann Gruber
<fl.formal-languages><automata-theory>
Languages whose Parikh image is recognizable
StefanH
# Languages whose Parikh image is recognizable

(Asked by: username_0 on 2020-04-18)

Let $\Sigma$ be some alphabet, and $p : \Sigma^\* \to \mathbb N\_0^{|\Sigma|}$ the [Parikh map](https://en.wikipedia.org/wiki/Parikh%27s_theorem#Definitions_and_formal_statement). A formal language $L \subseteq \Sigma^\*$ is called a *slip*-language, if $p(L)$ is a [semilinear set](https://en.wikipedia.org/wiki/Generalized_arithmetic_progression#Semilinear_sets). By [Parikh's theorem](https://en.wikipedia.org/wiki/Parikh%27s_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](https://en.wikipedia.org/wiki/Rational_set). The [recognizable set](https://en.wikipedia.org/wiki/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](https://www.sciencedirect.com/science/article/pii/S0022000071800247), and such neat results as that the commutative closure of binary slip languages is [context-free](https://www.sciencedirect.com/science/article/pii/S0166218X03003354).

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

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: I'm not sure if it will give you a clear answer, but a lot of the concepts you mention arise often when studying VASS (vector addition systems with states). Perhaps some of the results there will shed light on this.  
> **username_0**: @Shaull Thanks. At least it gives me a direction to look for :) Btw, if you know some specific resources/surveys about VASS, feel free to share them!  
> **username_2**: VASSs are mentioned often in https://cel.archives-ouvertes.fr/cel-00727025v2  
> **username_3**: I vaguely remember the concept of Parikh automata, as discussed here. http://cds.cern.ch/record/1321204?ln=en However, I cannot tell how well that automaton model fits with your question.  

---

## 1 answers

### Answer by username_0 on 2021-02-21. Score: 4 | Accepted answer

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](https://www.ams.org/journals/proc/1966-017-05/S0002-9939-1966-0201310-3/S0002-9939-1966-0201310-3.pdf), Amer. Math. Soc. 17 (1966), 1043-1049.

Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin:
[Regular languages and partial commutations](https://www.sciencedirect.com/science/article/pii/S0890540113000771?via%3Dihub). Inf. Comput. 230: 76-96 (2013)


---

