HOW NOT TO ESTABLISH COMPLEXITY BOUNDS FOR THE CONTEXT FREE LANGUAGES
Original Publication Date: 1976-Jul-31
Included in the Prior Art Database: 2007-Apr-01
Software Patent Institute
Lewis, F.D.: AUTHOR [+2]
HOW NOT TO ESTABLISH COMPLEXITY BOUNDS FOR THE CONTEXT FREE LAXGUAGES* F. D. Lewis
HOW NOT TO ESTABLISH COMPLEXITY BOUNDS
FOR THE CONTEXT FREE LAXGUAGES*
F. D. Lewis
Technical Report 76-2
State University of New York at Albany
*This research was supported in part by a SUNY Research Foundation
The complements of sets constructed by diagonalization
are called productive sets. No context free language can be
productive with respect to any space complexity class.
Therefore simple diagonalization cannot be used to show com-
plexity bounds for context free languages.
1. ~ntroduction. One of the most popular methods for esta-
blishing non-membership in a class of sets or languages is
diagonalization. A set is constructed which systematically
disagrees with each member of the class and therefore cannot
be a member of the class. Many examples of this are found in
In his classic paper [61, Post discovered that the
complements of the "diagonal" sets for the recursively enumerable
sets possessed a rather spectacular property: productiveness.
DEFINITION., The set A is productive with respect to the class
of sets B1,B2,B3, ... iff there is a function p such that for
all Bi:BiG A implies that p(i)~A,-Bi.
The function p is known as thêroductive
function for the class
of Bi and in fact provides a witness [namely p(i) 1 to the fact
that no Bi is exactly the set A.
Productiveness with respect to the recursively enumerable
sets is discussed in detail in [71 and introduced subrecursively
in 141. If the class of sets whose characteristic functions,lare
computable on Turing machines in space t is denoted R,(t) then
~,(t)-productivenessvia string substitution functions [otherwise
known as homomorphismel can be defined:
DEFINITION. The set A is R, (t)-productive iff there is a string
substitution function p such that if i is the description of a
Turing machine which computes the characteristic function of some
set B in space t then BGA implies that p(i)EA-B.
The other preliminary notion needed in this note is
reducibility. This currently popular concept also goes back to
Post  and is treated in detail in .
DEFINITION. The set A is many-one reducible to the set B
[denoted A B] via the function f .iff:
It should be pointed out here that when the above f is a
string substitution function [or homomorphism] that space complexity [below exponential] and productiveness are preserved by these mappings .
2. Context free language bounds.
- Greibach has exhibited a
"hardest" context free language [l] and this language: Lo
has the property that a language is context free iff it is reducible [via a string substitution function] to L 0' Since reducibility preserves productiveness, i f an...