Puzzle 1

The first 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), \ldots, (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 \ldots i_n$ of indices, where each $i_j \in \{1,2,\ldots,k\}$ such that $u_{i_1}u_{i_2}\cdots u_{i_n} = v_{i_1}v_{i_2}\cdots v_{i_n}$.

A weak match of a correspondence system $\{(u_1,v_1), (u_2,v_2), \ldots, (u_n,v_n)\}$ is a string $w$ such that, for some $n > 0$, $i_1,i_2,\ldots,i_n$, $j_1,j_2,\ldots,j_n$ where $1 \leq i_1,\ldots,i_n,j_1,\ldots,j_n \leq k$

$u_{i_1}u_{i_2}\cdots u_{i_n} = v_{j_1}v_{j_2}\cdots v_{j_n} = w$.
$i_1 i_2 \ldots i_n$ is a permutation of $j_1 j_2 \ldots 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?

Solution sketch

As yet we do not know how to solve this problem. We present a solution to a simpler variant of this problem: Given a set of pairs of strings $(u_1,v_1), \ldots, (u_n,v_n)$ do there exist integers $i_1,i_2,\ldots i_k$ and $j_1,j_2,\ldots j_k$ such that $u_{i_1}u_{i_2}\ldots u_{i_k} = v_{j_1}v_{j_2}\ldots v_{j_k}$. In other words, we just want to pick the same number of elements from each list, without any special connection between the two sets of elements picked.

The solution given below reduces the problem to that of deciding the emptiness of the language accepted by a nondeterministic pushdown automaton. The NPDA operates as follows: As it reads its input it parses it using elements of the $u_i$'s as well as elements of the $v_i$'s and uses the stack to keep track of the difference between the number of elements of $u_i$'s used in the parsing and the number of $v_i$'s used in the parsing (If $u_i$'s have been used up in excess then as many $1$'s as there have been extra $u_i$'s are stored in the stack and, on the other hand, if $v_i$'s have been used up in excess then as many $0$'s as there have been extra $v_i$'s are stored in the stack.)

The automaton accepts a string, if at the end of reading the entire string it has been fully parsed in terms of $u_i$'s and $v_i$'s (a condition on states) and the number of $u_i$'s used in parsing it is the same as the number of $v_i$'s used in parsing it (the stack is empty). Thus a string is accepted iff it is a solution to the problem described above. It is an easy exercise to turn such an automaton into an equivalent traditional NPDA that accepts by final states (or equivalently empty stack).

K Narayan Kumar, SMI, Chennai
kumar@smi.ernet.in