arvind@utcsri.UUCP (07/22/87)
Date: Tue 21 Jul EDT 1987 12:07
From: Martin Tompa <tompa@ibm.com>
Subject: LOGCFL
Using a method very similar to Neil Immerman's, I have a proof that
LOGCFL is closed under complementation. The main difference is that,
instead of counting the number of configurations reachable from the
initial configuration, it seems that one must count the number of
realizable pairs of surface configurations. This requires a little more
bookkeeping than Neil's proof, but the outline is exactly the same. For
example, in order to check whether (u,v) is realizable by a computation
of length at most d+1, given the number of pairs realizable by
computations of length at most d, one of the things that must be done is
the following: Cycle through all possible pairs (h,i) counting those
that are realizable by some computation of length b at most d. For each
such (h,i), cycle through all possible pairs (j,k) counting those that
are realizable by some computation of length c at most d. For each such
(j,k), check whether u=h, i=j, k=v, and b+c is at most d+1.
For pebbling enthusiasts, here is a curious consequence. One can define
a LOGCFL hierarchy whose SIGMA1 is LOGCFL, and whose SIGMA(i+1) is
LOGCFL with an oracle for SIGMAi. It turns out that SIGMAi is
equivalently the set of languages recognizable by polynomial size
uniform circuits that can be pebbled in the dual 2-person pebble game
with constant pebbles, O(log n) time, and i-1 role switches. Of course
this hierarchy collapses to SIGMA1 (perhaps the shortest-lived of all
hierarchies). As a consequence, 0 role switches are as powerful as any
constant number.