# PCP with commutative alphabet

Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable. Is the following variant also known to be undecidable?

PCP with commutative alphabet. Given and alphabet $$\Sigma = \{a_1, a_2, \ldots, a_K\}$$ and $$2N$$ sequences $$\gamma_1, \gamma_2, \ldots, \gamma_N, \delta_1, \delta_2, \ldots, \delta_N \in \Sigma^*$$. Determine if there is a sequence of integers $$\{i_j\}_{j=1}^M$$ such that for each $$1 \leq j \leq M$$, $$i_j \in \{1, 2, \ldots, N\}$$ and for each $$1 \leq m \leq K$$,

$$\#(a_m, \gamma_{i_1} \gamma_{i_2} \ldots \gamma{i_M}) = \#(a_m, \delta_{i_1} \delta_{i_2} \ldots \delta_{i_M})$$ where $$\#(a, w)$$ denotes the number of occurences of the symbol $$a$$ in the string $$w$$.

Notice why I used the term "commutative" for the alphabet: the order of the symbols in the strings does not matter; only the counts need to be equal.

In general, is any variant of (unbounded) PCP with commutative alphabet known to be decidable or undecidable?

• In the paper you link it is mentioned (on page 358): "The only known (positive) result related to PCP with commutative alphabet is of [12] and deals with the Parikh equivalence, i.e. the case when the p.c. alphabet is fully commutative." – Hendrik Jan Dec 18 '18 at 12:46

Let $$\gamma_{ij},\delta_{ij}$$ be the number of characters $$\sigma_j$$ in $$\gamma_i,\delta_i$$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $$a_1,\ldots,a_N,b_1,\ldots,b_N$$ such that for all $$j \in \{1,\ldots,K\}$$, $$\sum_{i=1}^N a_i \gamma_{ij} = \sum_{i=1}^N b_i \delta_{ij}.$$