sloan@uicbert.eecs.uic.edu (Bob Sloan) (02/09/91)
Does anybody know whether the following variation of the Post Correspondence Problem is decideable: As usual, we have two numbered lists of strings. The question is, can we find two (rather than one) equal-length sequences of integers (an integer may appear more than once is either sequence) such that the two corresponding sequences of concatenated strings are identical? Note: If the equal-length restriction is removed, then this problem reduces to the NP intersection problem for finite state automata and is therefore certainly decidable.