[comp.theory] Post Correspondence type problem

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.