In this section I show that the *p*-parsing problem
for
()-grammars is generally not
solvable. A yes-no problem is *undecidable* (cf.
[33, pp.178-179]) if there is no algorithm that
takes as its input an *instance* of the problem and determines whether
the answer to that instance is `yes' or `no'. An instance of a
problem consists of a particular choice of the *parameters* of
that problem.

In the case at hand I show that in general the
*p*-parsing problem is not solvable for any fixed path *p*.
I show that this result holds both for the *p*-parsing problem,
and goals in general.
I encode an undecidable problem in
a
()-grammar in such a way that deciding whether there is at least
one solution of the *p*-parsing problem will be equivalent
to solving this undecidable problem.

I use Post's Correspondence Problem (PCP) as the undecidable problem. The following definition and example of a PCP are taken from [33][chapter 8.5].

An instance of PCP consists of two lists,
*A* = *v*_{1}...*v*_{k} and
*B* = *w*_{1}...*w*_{k} of strings over some alphabet . This instance
has *a solution* if there is any sequence of integers
*i*_{1}...*i*_{m}, with *m*
1, such that

The sequence
*i*_{1},..., *i*_{m} is a solution to this instance of PCP.
As an example, assume that
= {0, 1}. Furthermore, let
*A* = 1, 10111, 10
and
*B* = 111, 10, 0. A
solution to this instance of PCP is the sequence
2,1,1,3 (obtaining the sequence 101111110). For an illustration, cf. figure 2.11.

Clearly there are PCP's that do not have a solution. Assume again that
= {0, 1}. Furthermore let
*A* = 1
and
*B* = 0. Clearly this PCP does not have a solution. In
general, however, the problem whether some PCP has a solution or not
is not decidable. This result is proved by
[33] by showing that the halting problem for
Turing Machines can be encoded as an instance of Post's Correspondence
Problem.

First I give a simple algorithm to encode any instance of a PCP as a
grammar of
(), in such a way that the question whether there is a
solution to this PCP can be phrased as a *goal*. Then I extend the
encoding in such a way that the question whether there is a solution
is equivalent to the *p*-parsing problem.

Note that I use the notation
*l*^{i} to stand for *i* repetitive
occurrences of label
*l*. Hence the expression
X_{0} *a* *in* *r*^{4} *f* will stand for the
path
X_{0} *a* *in* *r* *r* *r* *r* *f*.
Furthermore I assume that *C* and *L* are defined appropriately.

- 1.
- For each
1
*i**k*(*k*the length of lists*A*and*B*) define a unit rule*sign*(X_{0})`:-`, where is defined as follows (the*i*-*th*member of*A*is*a*_{1}...*a*_{m}, and the*i*-th member of*B*is*b*_{1}...*b*_{n}).- (a)
- For each
*j*, 1*j**m*there is an equation: X_{0}*a**in**r*^{j - 1}*f*a_{j} - (b)
- Moreover, there is an equation:
X
_{0}*a**in**r*^{m}X_{0}*a**out*. - (c)
- For each
*j*, 1*j**n*there is an equation: X_{0}*b**in**r*^{j - 1}*f*b_{j} - (d)
- Moreover, there is an equation:
X
_{0}*b**in**r*^{n}X_{0}*b**out*.

- 2.
- There is one non unit rule, defined as follows:

The underlying idea of the algorithm is really very simple. For each pair of strings from the lists A and B there will be one unit rule where these strings are represented by a difference-list encoding. Furthermore there is a general combination rule that simply concatenates A-strings and concatenates B-strings.

The following goal then is equivalent to determining whether there is a solution to the PCP:

In matrix representation the resulting () grammar for the first example PCP above, look as in figure 2.12. Furthermore, one of the parse trees for the solution given above is presented in figure 2.13.

To show that the same result applies to the *p*-parsing problem I
change the encoding slightly. Firstly, each unit rule built by the
foregoing algorithm will have an extra constraint
X_{0} *solution*
no. Similarly, in the combination rule I add for each of the
three variables
X_{0},X_{1},X_{2} the constraints
X_{i} *solution*
no. Finally, the query above is then
encoded as an extra rule as follows:

Now, the question whether there is a solution to an instance of PCP can be
answered ``yes'' in case the enumeration of the *solution*-parsing problem of the
following formula at least yields one answer:

has at least one solution. By construction, there is a direct
relation to a solution to
(a list of integers) and a derivation
of
()(). A derivation encodes the concatenations of the
*a* and *b* strings. If and only if such a concatenation yields the
same list this derivation can be the daughter of the final rule. The
last problem however is known to be undecidable, hence the *p*-parsing
problem is unsolvable.

1998-09-30