Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!spool.mu.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!ceres.physics.uiowa.edu!news.iastate.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!sloan
From: sloan@uicbert.eecs.uic.edu (Bob Sloan)
Newsgroups: comp.theory
Subject: Post Correspondence type problem
Keywords: PCP
Message-ID: <1991Feb8.183340.13998@uicbert.eecs.uic.edu>
Date: 8 Feb 91 18:33:40 GMT
Distribution: comp
Organization: University of Illinois at Chicago
Lines: 13


	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.