Binary (generalized) post correspondence problem.
We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by Ehrenfeucht, Karhumki and Rozenberg. Our proof is complete and somewhat shorter than the original proof although we use the same basic. Copyright 2002 Elsevier Science B.V. All rights reserved.
Introduction
Let A and B be two nite alphabets and h; g be two morphisms
. The Post Correspondence Problem, PCP for short, is to determine if
there exists a nonempty word w 2 A  such that It was proved
by Post [8] that this problem is undecidable in general. Such a word w that
called a solution of the instance (h; g) of the PCP.
In the binary PCP we assume that the size of the instance (h; g) is two
2. This problem was proved to be decidable by Ehrenfeucht,
Karhumki and Rozenberg [2]. Here we shall give a new shorter proof to
this binary case, although we use the same basic idea as [2]. Our proofs are
combined from [4] and [3], and we have added details to the proof to make it
easier to read. Also, although we restrict to the binary PCP, we shall achieve
more information than really needed for the binary case.
Note that it is also known that if jAj  7, then the PCP remains unde-
cidable, see [7]. The decidability status is open for 3  jAj  6.
Another important problem is the generalized PCP, GPCP for short. It
consists of two morphisms . The
GPCP is to tell whether or not there exists a word w 2 A  such that
Here again w is called a solution. We shall denote the instance of the GPCP
by called the begin words and
called the end words. Note that also for the GPCP it is known
that it is decidable, if jAj  2, see [2], and undecidable, if jAj  7, see [6]. As
for the PCP, the decidability status of the GPCP is open for the alphabet
size between these two bounds.
The basic idea in [2] is that each instance (h; g) of the binary PCP is
either
(1) periodic, i.e.,
(2) it can be reduced to an equivalent instance of the binary generalized
PCP with marked morphisms,
and then it is proved that both of these two cases are decidable. Recall
that a morphism h is called marked if the images of all letters begin with
a dierent letter, i.e., h(x) and h(y) start with a dierent letter whenever
y.
For the decidability proof of the periodic case, see [2, 5]. We shall also
present a proof in the next section. We shall give a new proof to the second
case. In [2] it was proved that the binary GPCP is decidable for marked
morphisms. This proof is by case analysis and it is rather long. We shall
give here a new proof, which follows the lines of [3], where it was proved that
the GPCP is decidable for marked morphisms with any alphabet size. Since
here we shall concentrate only on the binary case, the decidability proof
becomes more elementary and shorter than that in [3].
Our proof for the decidability of the marked binary GPCP uses the idea
of reducing a problem instance to nitely many new instances such that at
least one of these new instances has a solution if and only if the original one
has. Then by iterating this reduction we shall nally get to (nitely many)
new instances, where the decision is easy to do.
Note that in the PCP and GPCP we may always assume that the image
alphabet B is binary, since any B can be injectively encoded to f0; 1g  . For
example,
is such an encoding. Therefore in the binary case we shall assume that
We shall rst x some notations. The empty word is denoted by ". A
word x 2 A  is said to be a prex of y 2 A  , if there is z 2 A  such that
This will be denoted by x  y. A prex of length k of y is denoted
by pref k (y). Also, if z 6= " in y = xz, then x is a proper prex of y, and,
as usual, this is denoted by x < y. We say that x and y are comparable if
x  y or y  x.
A word x 2 A  is said to be a sux of y 2 A  , if there is z 2 A  such
that This will be denoted by x 4 y and, if z 6= ", then x is called a
proper sux, denoted by x  y.
then we also denote that
2 The periodic case
We shall begin with the easier part of the solution and consider rst the
instances of the (binary) PCP, where one of the morphisms is periodic. To
prove this result we shall need lemma, which states a property of the one
counter languages or context-free languages, see [1].
Lemma 1. Let  : A  ! Z be a monoid morphism into the additive group
of integers and let R  A  be a regular language. It is decidable whether
Proof. Here the language  1 (0) is a one counter language and one counter
languages are closed under the intersection with regular languages. The
emptiness problem is decidable for one counter languages and even for context-free
languages, see for example [9].
The proof of the next theorem is from [5], see also [2].
Theorem 1. PCP is decidable for instances (h; g), where h is periodic.
Proof. Let and assume that h is periodic and
a word . Dene a morphisms  by
for all a 2 A. Dene a regular set f"g. Now
and w 2  1 (0) \ R if and only if w 6= ", g(w) 2 u  and In
other words we have
;. By Lemma 1 the latter property is decidable and therefore the claim
follows.
Note that the above proof holds for all alphabet sizes, not only for the
binary case.
3 From PCP to GPCP
be a morphism that is not periodic. Dene the
mapping h (1) by
In other words the images of h (1) are the cyclic shifts of the images of h.
Now dene recursively h
For any two words u; v 2 A  it is well known that uv = vu if and only if u
and v are powers of a common word. It follows from this that the maximum
common prex of h(01) and h(10) has length at most jh(01)j 1.
Lemma 2. Let z h be a maximum common prex of h(01) and h(10) and
is a marked morphisms and h (m)
all w 2 f0; 1g  . Moreover, for any w, if jh(w)j  m, then z h  h(w).
Proof. We may assume by symmetry that jh(1)j  jh(0)j. Assume rst that
clearly, h (m) (0) and h (m) (1) begin with dierent letters
by the maximality of the z h .
If m  jh(0)j, then
juvj  jh(0)j, and ux  h(0) and We have two possibilities,
either m  jh(1)j or m > jh(1)j.
Now h (m)
and since v and x begin with dierent letters, h (m) is marked, see also Figure
1.
We still need to prove that h (m) is a morphisms. This follows since
and
Therefore for all w 2 A  , h (m)
h h(w)z h , and the last part of the
claim follows directly from this.

Figure

1: Case
Note that if h is already marked, then z
Let (h; g), where h; be an instance of the binary
PCP. Assume further that h and g are nonperiodic. Let z h be as above,
j. We may assume by symmetry that m  n. We now
have the following lemma.
Lemma 3. The instance (h; g) of the binary PCP has a solution if and only
if the instance ((z 1
z h )) of the binary GPCP has a
solution.
Proof. It is obvious that if an instance (h; g) of the PCP has a solution,
then z g  z h . This can be seen if we assume that w is solution such that
Assume rst that the instance of the GPCP has a solution w, i.e.,
z h h (m)
z h
and therefore
This is true if and only if
Assume then that (h; g) has a solution w. Since h (m) and g (n) are mor-
phisms, we get that
g(w)z g )z 1
and therefore
z h h (m) (w)z 1
This is true if and only if
z h )h (m)
z h
This proves the claim.
Marked PCP
In this section we shall consider the solution method to the marked (binary)
PCP. The proofs of the lemmata in this section are from [4], and we shall
prove the results for all alphabet sizes.
A block of an instance I = (h; g), where h; , of the marked
PCP is a pair (u; v) 2 A such that
prexes v. If there is
no danger of confusion, we will also say that is a block. A letter
is a block letter if there is a block (u; v) such that a  h(u) and b  g(v).
In other words, b is the rst letter of the images of a block. Accordingly, a
block is a minimal nontrivial solution of the equation
Lemma 4. Let (h; g) be an instance of the marked PCP for h;
Then for each letter a 2 A, there exists at most one block (u; v) such that
a  u. In particular, the instance (h; g) has at most jAj blocks. Moreover,
the blocks of (h; g) can be eectively found.
Proof. Consider any pair (u; v) of words such that h(u) and g(v) are comparable
and h(u) 6= g(v). Since h and g are marked, there exists a unique a 2 A
such that h(ua) and g(v) or h(u) and g(va) are comparable if h(u) < g(v) or
g(v) < h(u), respectively. Since the morphisms are marked, it is clear that
the rst letter of u determines uniquely the rst letter of v and the claim
follows from this inductively.
The latter claim is evident, since fu is a regular
set.
be an instance of the marked binary PCP with h;
is a block letterg: (1)
Note that jA 0 j  jAj although A 0  B, since there are at most jAj blocks by
Lemma 4.
We dene the successor of I to be I
and g 0 are from  such that
where (u; v) is a block for the letter a 2 A 0 .
Lemma 5. Let I = (h; g) be an instance of the marked PCP and I
be its successor.
I 0 is an instance of the marked PCP.
(ii) I has a solution if and only if I 0 has.
Proof. (i): This is clear since the dierent block words for h (and g) begin
with dierent letters.
Assume that I has a solution w. Then w has two factorizations,
some letter a is a solution for I 0 ,
since h 0 (w
Assume that I 0 has a solution w . Then there are blocks
is a solution of I.
k. By the
denitions, for all x i there exists a block
Therefore the claim follows.
The denition of a successor gives inductively a sequence of instances I i ,
where I I and I
. Note that the reduction of an instance I to its
successor I 0 was already used in [2], but the reduction was done only once.
The dierence here is that we shall iterate this reduction. The decidability
of the marked PCP in [4] was eventually based on the fact that the successor
sequence dened above has only nitely many distinct instances. The authors
of [4] used two measures for an instance I of the marked PCP, namely
the size of the alphabet and the sux complexity :
It is clear that for alphabet sizes of I 0 and I we have jA 0 j  jAj. Note that
if we are studying the binary case, then we know that if the alphabet size
decreases, then we get to the unary case, where the PCP becomes decidable.
That is not so straightforward.
Lemma 6. If I is an instance of the marked PCP and I 0 is its successor
then
Proof. Let
. Then there exists at least one block (u; v), where s 4 v. Let
H be a function, where p(s) is the z above with the minimal
length. By the markedness this z is unique and therefore p is an injective
function. Similarly we can dene an injective function from H 0 to G. The
claim follows by the injectivity.
The previous lemma together with jA 0 j  jAj yields the following result.
Lemma 7. Let I be an instance of the marked PCP. Then there exist numbers
d such that I i+d = I i for all i  n 0 . The numbers n 0 and d can
be eectively found.
The previous lemma means that after n 0 consecutive successors the instances
begin to cycle: I n 0
Lemma 8. The sequence I has the following properties.
(i) The size of the alphabet is constant and
(ii) The instance I 0 of the marked PCP has a solution if and only if, for
all i  n 0 , I i has a one letter solution.
Proof. The case (i) follows from the denition of n 0 .
For (ii), we may assume that n By the proof of Lemma 5, case (ii),
for every solution x i to some I i , there is a solution x i+1 to I i+1 such that
solution of a minimum length
to I 0 . Now by the above relation between the solutions, there is a solution
x d to I d , where d is as in Lemma 7 such that
Since the g i and h i cannot be length-decreasing, we have jx 0 j  jx d j. But
chosen to be a minimum length solution and x d is also a solution
to I d = I 0 , and therefore necessarily jx and the morphisms g 0 (=
the letters occurring in x d to letters.
But then the rst letter of x d is already a solution to I 0 and by the proof
of Lemma 5 all instances in the loop have a one letter solution. This proves
the case (ii).
Theorem 2. The marked PCP is decidable.
Proof. By constructing the successor sequence we will meet one of the following
cases: (1) the alphabet size is one, (2) the sux complexity goes to
zero or (3) we have a cyclic sequence. The rst two are easy to decide, and
by Lemma 8 we can decide the third case by checking whether there is a
solution of length one and the claim follows.
Note that we can also decide, whether an instance of the marked PCP
has a solution beginning with a xed letter a, since we may map back the
found one letter solutions as in the proof of Lemma 8 and check whether one
of these begins with a.
5 Block structure in the marked binary GPCP
The instances
of the (binary) GPCP can be reduced to instances, where
and since to have a solution we must have
We shall extract the denition of the successor of the marked (binary)
PCP to the marked (binary) GPCP. All denitions in this section apply for
any alphabet size, not only for binary, therefore we use arbitrary alphabet
A as the domain alphabet, and whenever we consider only the binary case
it shall be mentioned.
If the instance of the PCP is neither marked nor periodic, then we transform
it to an instance of the marked GPCP as was done in Section 3.
Assume that we have an instance
For we construct the blocks for (h; g) as in the case of the PCP. We
shall also construct the so called begin block (x; y), where p 1
and there does not exists r < x and s < y such that p 1
that the begin block is unique and, if
For the end words s called
an end block (or an block, to be precise) if h(u)s
not a block for any u 1  u and v 1  v. Let
is an end block and a  h(u) or a  g(v)g
be the set of all end blocks for the letter a 2 A.
Lemma 9. Let I be an instance of the marked
a be a xed letter. The set of end blocks
E a is a rational relation and can be eectively found. Moreover,
(i) If a is a block letter, E a is nite.
(ii) If E a is innite, then it is a union of a nite set and nite number of
sets
for some words u; v; x;
Proof. Without loss of generality we may assume that s ". The end blocks
can be found similarly as we found the blocks for a letter a: we check rst if
v. If so, ("; v) is an end block. Then we construct
the sequence
are always comparable (as in Lemma 4). Whenever h(u i )z
some z i  s 1 , we can check if there is a word w i such that h(u i )s
If such a w i exists, it is unique because g is marked. Consequently
is an end block. Notice that i is not necessarily unique.
If a is a block letter for a block (u; v), then always u i  u and v i  v
and the sequence terminates. But then there are only nitely many
possible z i such that h(u i )z . The claim (i) follows
hereby.
By the above considerations, if E a is innite, then a is not a block letter,
and the sequence in order to get innitely many possible
z i . This is possible only if there are words x;  such that
we have
end block is of form jyj, an end block can always
be written as (xu k u equivalently as (xu 0 (u 00
to get the desired form (here
since there are only nitely many prexes u 0 and v 0 and there are at most
potential end blocks. The rationality of E a follows from the
proofs for (i) and (ii).
We shall call (xu k ; yv k w) and (xu k w; yv k ) in Lemma 9 (ii) extendible end
blocks.
be an instance of the marked GPCP. For
a solution w
is a block decomposition for w, if
is the begin block
for each
is an
Because the blocks are minimal solutions to h(u i is easy to see
that the following lemma holds.
Lemma 10. Every solution w 2 A  of I has a unique block decomposition.

Figure

2: Block decomposition of a solution w
Note that, since the block decomposition of a solution may consist only
of an end block, it is necessary to construct also the set
where (x; y) is the begin block. Moreover, if the begin block does not exist,
can be innite as in Lemma 9. This case will be studied in Lemma 12.
be an instance of the binary marked
GPCP. In the binary case we have three choices for a solution:
(0) There are no blocks in the solution.
(1) Exactly one block is used in the solution.
(2) Two blocks are used in the solution.
Here the expression 'used blocks' mean the number of dierent blocks in the
block decomposition.
We shall use the next lemma to prove that the solutions of the type (0)
and (1) can be eectively found.
Lemma 11. Let x; A  be xed words. It is decidable, whether
the pair (xu k w; yv k z) is a solution to I for some k > 0, i.e., whether
Proof. If (xu k w; yv k z) contains a solution for some k, then
We obtain
where the left-hand side does not depend on k. Now if this equation holds,
then either or there is a unique k satisfying it. Therefore
we assume that since in the other case the uniqueness of k
guarantees the decidability.
Now if (4) holds for some k, then it holds for all k. And consequently
and the dierence jp 1 h(xu k w)j
constant. We may assume by symmetry that jp 1 h(x)j >
' be the least number such that jp 1 g(yv ' )j > jp 1 h(x)j. Now,
since the possible overow in p 1 h(xu k w) and p 2 g(yv k z) is unique
by the length argument.
We have proved that if there are at most '+1 dierent
cases to check for solutions. Clearly these instance can be decided, since we
have either one or ' to check whether
and xu k z. And since this ' can be eectively found, we have proved
the claim.
For the case (0) we prove
Lemma 12. Let I be an instance of the marked binary GPCP as above. It
is decidable, whether I has a solution of type (0). Moreover, it is decidable,
contains a solution.
Proof. If I has a solution w of type (0), then (w; w) is either in E p or
is the begin block and is an end block.
In other words, we need to check whether there is solution of these forms.
Consider the set E p rst. If E p is nite than the decision is easy.
Therefore we assume that there is an extendible end block (xu k w; yv k ) or
. By Lemma 11, it is decidable whether the extendible end
block contains a solution (note that z = "), and since, by Lemma 9(ii), there
may exist only nitely many extendible end blocks, we have completed the
rst part of the proof.
In the second case, the solutions of the form
is an end block, also reduces to Lemma 11.
Since the begin block is unique, the end blocks are the ones to consider. If
the number of end blocks is nite, then the decision is easy. And if there is
an extendible end block, say (xu k w; yv k ), then we search for the solution in
0, and this can be done by Lemma 11 (replace x
by
We can also prove that the solutions of the type (1) can be eectively
found. This is a consequence of Lemma 11.
Lemma 13. It is decidable, whether an instance of the marked binary GPCP
has a solution of type (1).
Proof. Assume that only one block is used in the solution, i.e., the solution
w is of the form is the begin block, (t; s)
is a block for some letter a and is an end block. Now for a xed end
decision, whether there is a solution in the (t 1 t ' t
for ' > 0, can be done by Lemma 11.
In the solutions of the type (1), the harder case seems to be the possible
extendible end block. Assume therefore that there is an extendible end block
9 and the fact that h and g are marked, the block
(t; s) and this extendible end block necessarily begin with dierent letters.
We should now decide whether for some ' and k,
solution. But also this case reduces to Lemma 11. We have two cases, assume
rst that t 1 t n 6= s 1 s n for all n. Then, for all n, there is a non-empty overow
the words are comparable. If the
words are not comparable for some n, then there is no solution for '  n.
Now the rst letter of r is what makes ' unique in this case. Assume that
there is such an ' for which we have a solution. Then for the rst letter
of r is equal to the rst letter of xu or yv, which is dierent from the rst
letter of t or s, respectively. Therefore t 1 t '+1 and s 1 s '+1 are not comparable,
and there cannot be solutions for the powers greater then this xed '.
We can eectively nd such an ', if we construct the pairs of words
In other
words, we construct the solution as the blocks. Now there are only nitely
many dierent overows in these pairs and if suitable possible overow exists
we can nd it. On the other hand, if no such overow exists, then we will
have a same overow twice or the pair is no longer comparable. And since '
is unique, we may replace x with
the decidability follows.
The other case is that, for some n,
there now is a solution, then necessarily t m xu k
and k. Moreover, if jtj 6= jsj, then m is unique as '
in the previous case if it exists. And if then it is enough to check,
whether which can be done by
Lemma 11.
As a corollary we get
Corollary 1. The unary GPCP is decidable.
Proof. Since all the solutions of the unary GPCP are of the type (0) or (1),
the claim follows from Lemmata 12 and 13.
From now on we shall concentrate on the type (2) solutions. Note that
in this case no extendible end block may occur by Lemma 9.
Next we dene the successors of the instances I
of the marked GPCP. Assume that the begin block (x; y) exists, and that
x  y or y  x and set p 0
Let be the successor of (h; g) and let (u; v) be any end block of I.
Then
I 0 (u;
is the successor of I w.r.t. (u; v), where (s 0
2 ) is dened as follows: if
Otherwise I 0 (u; v) is not dened.
Lemma 14. An instance I has a solution if and
only if the successor I 0 (u;
2 )) has a solution for
some end block (u; v). Moreover, each solution w to I can be written as
is a solution of I 0 , (x; y) is the begin
block and (u; v) an end block of I.
Proof. Assume rst that I has a solution w with the block decomposition
where for the letter a i , for 2  i  k, is the begin
block and (u is an end block. Clearly u 1  v 1 or v 1  u 1 and
. If the rst cases hold, then p 0
and s 0
k+1 and I 0 (u;
i.e., I 0 (u; v) has a solution w
The other cases are similar.
Assume then that
I 0 (u;
has a solution w
is the begin block, and by Lemma 5 (iii),
and so xh 0 (w 0 is a solution of I.
Note that if the begin block does not exists, then there is no succes-
sors, and the only possible solutions are in E p , but this case is decidable by
Lemma 12. On the other hand, if the end words disappear, the instance is
decidable by the next lemma.
Lemma 15. Let I be an instance of the binary
GPCP. For the cases, where s ", the GPCP is decidable.
Proof. Let # be a new symbol not in f0; 1g. Extend the morphisms h and
g in a following way,
Now (h; g) is an instance of the marked PCP, and we can decide whether or
not it has a solution beginning with #.
6 Cycling instances
By Lemma 14 we can reduce an instance I to its successors for all end blocks.
The problem in this approach is that by Lemma 9, I potentially has innitely
many successors. But if there is an extendible end block, then the solutions
of the instance are necessarily of type (0) or (1) and these instances are
decidable by Lemmata 12 and 13. Therefore we may concentrate on the
case where there are no extendible end blocks and, since the unary GPCP is
decidable, the alphabet size is 2.
By Lemma 14, I has a solution if and only if one of the successors has. If
the sux complexity goes to zero at some step , then we can always decide
the successors letters a). Thus we can solve the
original problem. Otherwise, by Lemma 7, there is a number n 0 such that
the morphisms start to cycle.
Clearly to decide the marked binary GPCP it suces to show how to solve
these cycling instances, where the morphisms are binary.
By a successor sequence we mean a sequence
of instances of the marked GPCP such that each
is a successor of ((p (i)
Notice that if I
is the set of all pairs of
end words, is the set of all ith members in the successor sequences, we can
assume that
(A) There is a begin block for all i and
For, if the condition (A) does not hold, we know that no instance in I i+1
is dened and the only possible solutions are in E p and if (B) is not satised
by an instance, then that instance reduces to the marked PCP, which is
decidable by Lemma 15.
We shall next show how to treat the instances that begin to cycle, i.e.,
there exists a d such that for all successor sequences
We shall call such an instance I 0 a
loop instance, and d as the length of the loop. Notice that also (p (i)
(p (i+d)
2 ), since the begin words are constructed as the blocks and therefore
for some d the begin words and the morphisms are the same as in some
previous instance.
Notice that, since, by Lemma 8, the alphabet size does not decrease,
there is a block for both letters in f0; 1g. In particular, there cannot be
extendible end blocks.
Lemma 16. Assume that the instances cycle as in (5) and that a solution
exists. Then we have two cases:
(i) If p (0)
2 then the minimal solution of I 0 is w, where the initial
letter a of w satises h 0 (a) 6= g 0 (a). Hence h i (a) 6= g i (a) for all i  0.
(ii) If p (0)
, then a minimal solution w does not have a prex u such
that p (0)
Proof. The case (i) follows from Lemma 8, since the marked PCP has a
solution if there is a solution of length one. For the case (ii), if there exists
such a u, then p (k)
2 for some k , and therefore the same holds for
all j  k. But, since the instance is cycling, (p (0)
t  k, and we get a contradiction, since p (0)
.
Hereafter we will assume that p (0)
2 , since the case (i) reduces to
the (cycling) instances ((h(a); g(a)); h
for each a such that
We would like to have some upper bound for the lengths of the new end
blocks in the loop (5). We demonstrate that there is a limit number L such
that, if a solution exists, then the minimal solution is found in some sequence
shorter than L. Moreover, this limit can be eectively found, and the
main result follows from this.
In what follows, we assume that I = ((p has a minimal
solution such that p 1 which does not have u as a prex. Then
this minimal solution is unique, since we assumed that p 1 and the
morphisms are marked. Consequently each I has a unique end block (u; v)
in the block decomposition of the minimal solution. It follows that there
exists a unique successor sequence I of instances such that
I
where is the end block of the minimal solution of I i . This successor
sequence is called the branch of the minimal solutions. Note that we cannot
determine, which is the end block of the minimal solution, but the desired
limit will be obtained anyway.
Let I
be an instance in the branch of the
minimal solutions and w i be the minimal solution of I i . Recall that we
permanently assume that s (i)
2 , which implies that also
2 for each i.
Lemma 17. Let w i be the minimal solution of I i and let
(p (i)
each i.
Proof. The instances
I
share the begin block and the marked morphisms, so clearly w i  w i+d or
since the minimal solutions cannot have u, such that p (')
(u), as a prex (recall that p (i)
2 )). If w is a minimal solution to
some instance I, then by Lemma 14, there is a solution w 0 to the successor
of I such that
(and p (i)
consequently jwj > jw 0 j, because the
morphisms are nonerasing. Hence jw Inductively, jw i+t
all t, which proves the claim.
As a byproduct we obtain
Lemma 18. If an instance occurs twice in a successor sequence, it has no
solutions.
Proof. By the proof of the previous lemma, the length of the minimal solution
decreases strictly.
be an instance of the marked binary
GPCP. We assume now, by symmetry, that s 2 4 s 1 . An end block (u; v) of
the instance I satises the equation
. If this is an end block of a solution, then necessarily
the successor of I has the end
words
Lemma 19. Let I
2 )) be the branch of the minimal
solutions of a cycling instance with loop length d. Let also w i be the
minimal solution of I i . Then p (i)
2 is a prex
of p (i)
Proof. It suces to take the proof is analogous for all other values.
Recall also that s (t)
each t. By Lemma 17, w d  w 0 . Therefore
shall next prove
that jh 0 (w d )s (d)
)j. Assume on the contrary that jh 0 (w d )s (d)
)j. By the proof of Lemma 14,
and therefore
Hence
js (d)
This is a contradiction, since js (d)
It follows that jh 0 (w d )s (d)
similarly we can prove that jg 0 (w d )s (d)
loss of generality, we assume that s (d)
and since p (0)
are comparable and jh 0 (w d )s (d)
necessarily p (0)
s

Figure

3: Prex property
The previous lemma will be used in the proof our last lemma, which gives
an upper bound for the size of the end blocks in the branch of the minimal
solutions.
For an occurrence of a word u in g(w), its g-block covering in a solution w
of an instance ((p
that
1. is a factor of w,
2. u is a factor of z,
3. u is not a factor of g(v
4. for each i, g(v i
Note that a g-block covering for an occurrence of a factor u (in g(w)) is
unique. Hence we can dene the integer k to be the g-covering length of the
occurrence of u (in w).
Lemma 20. Let I
2 )) be the branch of the minimal
solutions of a cycling instance having loop length d. For all i  d,
then the h i+1 -covering lengths of s (i+1)
2 are at
most the g i -covering length of s (i)
1 .
then the g i+1 -covering lengths of s (i+1)
2 are at most
the h i -covering length of s (i)Proof. By Lemma 19, for i  d, the words s (i)and s (i)are covered by some
We will prove only the case (i), the other one is analogous. To simplify
the notations, we denote I = I
either I
We have to
show that in both cases, the h 0 -covering length of s 0 is at most the g-covering
length of s.
Assume that (u; v) is the end block of the minimal solution w of I. Let
also a  u be the rst letter of u. Then or u 4 v,
which gives us two cases to consider.
(1) If words u and v in the equation
are obtained during the block construction for a letter a. Because there also
is a block for letter a, necessarily s 0  h 0 (a), i.e. the h 0 -covering length of s 0
is 1 (see

Figure

4).

Figure

4: Picture of the case (1)
(2) Assume then that
rst that the g-covering length of the word g(s 0 ) is at most that of the word
s. This is clear, because g(s 0 ) shares with s every one of its block factors
(including the rst one, since as in the case (1), h(u) is covered by a
single g-block longer than h(u) (see Figure 5 for an illustration)),. We show
then that the h 0 -covering of s 0 is not longer than the g-covering of g(s 0 ), from

Figure

5: Block covering of )g(u). The vertical lines illustrate
the block covering.
which the claim follows. Let w 0 be the minimal solution of I 0 . Then the word
is a beginnning block for I, satises
and consequently w is a prex of the minimal solution of I. To show that the
-covering of s 0 is not longer than g-covering of g(s 0 ), it is sucient to show
that the block borderlines in dh 0 (w cutting s 0 can be mapped
injectively to block borderlines in p 1 h(w)g(s

Figure

6). Let now y 0  w 0 be a word that determines a block borderline in
and eg 0 (w
Now the word prex of w, since
and g is marked. But y also determines a block borderline in word p 2
cuts g(s 0 ), because
and hence p 1 h(w)  p 2 g(y). Notice nally that the word y determines z 0
uniquely, since g is injective and z 0 determines y 0 by eg 0 (z
that h is injective).
The previous lemma gives us a tool for recognizing instances which are
not in the branch of minimal solutions. Let I 0 be a cycling instance with loop
length d and consider all the instances I d found by the rst d reductions. If
I 0 has a solution then there is a unique I 2 I d in the branch of the minimal
solutions.
Let M be the maximal g- or h-covering length of all the end words s 1
and s 2 in I d . It now follows by Lemma 20 that in the branch of the minimal

Figure

Relation between g(s 0 ) and s 0
solutions the g i or h i -covering length is always less than or equal to M . For
a sequence of cycling instances, the sux complexity is constant
since the blocks of an instance I i are the images of the successor I i+1 , the
block length can never be more than 1. By the previous lemma we
have
Corollary 2. Let I be the branch of the minimal solutions of
a cycling instance with loop length d. For each i  d, the end words of I i are
not longer than M((I) 1).
7 Decidability results
Now we are ready to prove our main results.
Theorem 3. The binary marked GPCP is decidable.
Proof. We have already proved that the marked binary GPCP is decidable
in the unary case and the solutions of the type (0) and (1) can be found. It
remains to be shown how to nd the type (2) solutions, i.e., how to solve the
binary marked GPCP for the cycling instances I 0 .
A cycling instance has the blocks for the both letters and p (i)
all successors. In particular, there are no extendible end blocks and only
nitely many successors. The successor relation naturally denes a tree T
having I 0 as the root, all the successors of I 0 as the vertices and the pairs
as the edges.
The decision procedure is based on constructing T partially by rst inserting
the vertices having depth (the distance from the root) at most d
and then computing the number M , the maximal covering length of the end
words of instances at the depth d. For all vertices we check whether there
are solutions of type (0), (1) or an end block (u; v) 2 E p such that
And for all vertices ", we can
always decide if they have a solution by Lemma 15. If some such vertex I
has no solution, then I and all the successors of I can be removed. On the
other hand, if some such I has a solution, then I 0 also has a solution and
the procedure may stop.
For the vertices having depth greater than d, the (partial) construction
of T is more specic: Only the successors I
are inserted. By Corollary 2, the branch of
minimal solutions is included in the partial construction.
But now there are only nitely many instances to be inserted, so each
path (successor sequence) in the partially constructed T will eventually contain
an instance twice, thus I 0 has no solution by Lemma 18, unless some
vertex has a solution for some vertex (u; u)
As we saw in Section 3, the binary PCP is decidable if and only if the
binary marked GPCP is. Therefore Theorem 3 has the following corollary.
Theorem 4. The binary PCP is decidable.
Proof. First, if one of the morphisms is periodic, it can be decided by Theorem
1, and if the instance is marked, then it can be decided by Theorem 2.
Otherwise we construct the equivalent instance of the binary marked GPCP.
The binary marked GPCP is decidable by Theorem 3. The decision procedure
achieved reduces an instance of the binary marked GPCP to nitely
many simpler equivalent instances. By continuing this reduction to each reduced
instance we create a successor tree, where the decision is done in each
path separately according to the following seven rules:
(i) If we get unary successors, then we can decide these successors by
Corollary 1.
(ii) If we get an extendible end block, then the solutions are of the type
(0) or (1) and these cases can be decided by Lemmata 12 and 13,
respectively.
(iii) If we get end block (u; u), then s 0
this is decidable by Lemma 15.
(iv) If we get an instance which already occurred in the path, then the
instances in this path cannot have a solution by Lemma 18.
(v) If the lengths of the end words break the computable limit M((I 0 )+1),
then we do not have to continue this branch, since it is not in the branch
of minimal solutions by Corollary 2.
(vi) If we get an end block (u; u) in E p , then we have a solution. Also, if
there is no begin block then the possible solutions are in E p . These
cases are decidable by Lemma 12.
(vii) If there are no end blocks, then there are no solutions.
8 Conclusions and open problems
We have proved that in the binary case the Post Correspondence Problem is
decidable. Our solutions are on based on the construction of the successors,
which is equivalent to the original instance in the decidability sense. Then
after doing this reduction suciently many times we obtain instances, where
the decision is easy to do.
We note that an instance of the binary GPCP can also be reduced to
an instance of the binary marked GPCP using almost similar arguments as
in Lemma 3. Therefore we also gave a new proof to the decidability of the
binary GPCP.
As open problems we state the following immediate questions:
Decidability of the PCP and the GPCP in the ternary case, i.e.,
3.
Decidability of the strongly 2-marked PCP. A morphism is strongly
2-marked if each image of a letter has a unique prex of length 2. See
also [4].
There is also a very important open question considering the form of the
solutions of the binary PCP.
Let (h; g) be an instance of the binary PCP, where h is nonperiodic. Is
it true that all the solution are from the set fu; vg possibly
equal, words u and v? See also [5].



--R


The (generalized) Post correspondence problem with lists consisting of two words is decidable.
Generalizes PCP Is Decidable for Marked Morphisms.
Decidability and Undecidability of Marked PCP.
Morphisms. In Handbook of Formal Lan- guages
Remarks on generalized Post Correspondence problem.
Decision problems for semi-Thue systems with a few rules
A variant of a recursively unsolvable problem.
Formal Languages.
--TR
Formal languages
Morphisms
Marked PCP is decidable
Remarks on Generalized Post Correspondence Problem
Decision Problems for Semi-Thue Systems with a Few Rules

--CTR
Vesa Halava , Tero Harju , Juhani Karhumki, Decidability of the binary infinite post correspondence problem, Discrete Applied Mathematics, v.130 n.3, p.521-526, 23 August
Vesa Halava , Tero Harju , Juhani Karhumki , Michel Latteux, Extension of the decidability of the marked PCP to instances with unique blocks, Theoretical Computer Science, v.380 n.3, p.355-362, June, 2007
Vesa Halava , Tero Harju , Juhani Karhumki, Undecidability in -Regular Languages, Fundamenta Informaticae, v.73 n.1,2, p.119-125, April 2006
marked morphisms;decidability;binary post correspondence problem;post correspondence problem;generalised post correspondence problem