Puzzle 1
This problem asks whether a variant of Post's Correspondence
Problem (PCP) is decidable. Recall that an instance of PCP is a
list of pairs $\{(u_1,v_1), (u_2,v_2), ..., (u_k,v_k)\}$,
where each $u_i$ and $v_i$ is a word over $\Sigma$. A match for
the correspondence system is a sequence $i_1 i_2 ... i_n$ of
indices, where each $i_j \in \{1,2,...,k\}$ such that
$u_{i_1}u_{i_2}... u_{i_n} = v_{i_1}v_{i_2}... v_{i_n}$.
A weak match of a correspondence system $\{(u_1,v_1),
(u_2,v_2), ..., (u_n,v_n)\}$ is a string $w$ such that, for
some $n > 0$, $i_1,i_2,...,i_n$, $j_1,j_2,...,j_n$ where $1
\leq i_1,...,i_n,j_1,\ldots,j_n \leq k$
- $u_{i_1}u_{i_2}... u_{i_n} = v_{i_1}v_{i_2}... v_{i_n} = w$.
- $i_1 i_2 ... i_n$ is a permutation of $j_1 j_2 ... j_n$
That is, $w$ can be obtained by concatenating $n$ first
components and also by concatenating $n$ components. The exact
sequence of indices used in the two words may differ, but they
are required to be permutations of each other.
Is it decidable whether a correspondence system has a weak match?