Problem Detail: 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?
Asked By : Eli Rose
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23768
