4
$\begingroup$

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as:

$u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in \mathbb{N}\}$ where $u_i$ are vectors of natural numbers.

and a semi-linear set as a union of finitely many linear sets. It goes on to say ''For every semilinear set $S \subset N^k$, it is not hard to construct a regular set $R \subset \Sigma^*$ such that $\psi(R) = S$'' (where $\psi$ is the Parikh map, taking strings over an alphabet $\Sigma$ to vectors where the first entry is the number of the first letter, the second entry is the number of the second letter, etc. So $\psi(\{a, ab, ba, aaa\})) = \{(1), (1, 1), (3)\}$.)

I was trying to think why regular languages would be semi-linear instead of just linear, and it seems like the + (or) operation in regular expressions is to blame. Is this correct: are languages described by regular expressions which use only concatenation and $^*$ linear?

$\endgroup$
  • 3
    $\begingroup$ Have you tried proving your claim? That's the best way to know if you're right! $\endgroup$ – Yuval Filmus Apr 14 '14 at 2:46
4
$\begingroup$

Your claim is correct for a one letter alphabet $\Sigma = \{a\}$. We prove by induction that $\psi(r)$ is linear for every regular expression without addition. When $r = a$, $\psi(r) = 1$. When $r = r_1 r_2$, by the induction hypothesis $\psi(r_1) = u_0 + \sum_i \mathbb{N} u_i$ and $\psi(r_2) = v_0 + \sum_j \mathbb{N} v_j$, and so $\psi(r) = u_0 + v_0 + \sum_i \mathbb{N} u_i + \sum_j \mathbb{N} v_j$. When $r = r_1^*$, $\psi(r)$ is a subset of $\mathbb{N}$ closed under addition. Let $g = \operatorname{gcd}(\psi(r))$. Then $\psi(r)/g$ is a numerical semigroup, and so finitely generated, say $\psi(r)/g = \sum_i \mathbb{N} u_i$. So $\psi(r) = \sum_i \mathbb{N} gu_i$.

This argument doesn't quite work when $|\Sigma| \geq 2$, although there are some notions of GCD for multidimensional vectors, see for example this interesting presentation by Vadim Ponomarenko. Perhaps the argument above can be pushed through, or perhaps a different argument, which uses the fact that $\psi(r_1)$ is linear, exists. It's also possible that the claim is wrong in this case.

$\endgroup$
  • $\begingroup$ @GeorgZetzsche Perhaps you can find the error in the proof, then. Note that there could be more than one "period". $\endgroup$ – Yuval Filmus Jun 28 '16 at 6:09
  • $\begingroup$ Sorry, my mistake! :) $\endgroup$ – Georg Zetzsche Jun 28 '16 at 6:21
2
$\begingroup$

The claim fails for two symbols. The Parikh image $M\subseteq \mathbb{N}\times\mathbb{N}$ of $(abb^*)^*$ is not linear:

It is easy to see that for every finitely generated submonoid $N$ of $M$, there is a $k\ge 0$ such that for every $(x,y)\in N$, we have $x\le ky$ and $y\le kx$. This, however, is not satisfied by $M$ itself, meaning $M$ is not finitely generated.

Now as a submonoid of $\mathbb{N}\times\mathbb{N}$, $M$ is linear iff it is finitely generated.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.