5
$\begingroup$

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/5/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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Shaull May 6 at 20:27
  • $\begingroup$ @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! $\endgroup$ – StefanH May 6 at 20:47
  • 1
    $\begingroup$ VASSs are mentioned often in cel.archives-ouvertes.fr/cel-00727025v2 $\endgroup$ – Radu GRIGore May 7 at 6:41
  • $\begingroup$ I vaguely remember the concept of Parikh automata, as discussed here. cds.cern.ch/record/1321204?ln=en However, I cannot tell how well that automaton model fits with your question. $\endgroup$ – Hermann Gruber May 7 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.