Browse Prior Art Database

HOW NOT TO ESTABLISH COMPLEXITY BOUNDS FOR THE CONTEXT FREE LANGUAGES

IP.com Disclosure Number: IPCOM000149357D
Original Publication Date: 1976-Jul-31
Included in the Prior Art Database: 2007-Apr-01
Document File: 6 page(s) / 244K

Publishing Venue

Software Patent Institute

Related People

Lewis, F.D.: AUTHOR [+2]

Abstract

HOW NOT TO ESTABLISH COMPLEXITY BOUNDS FOR THE CONTEXT FREE LAXGUAGES* F. D. Lewis Technical Report 76-2 Computer Science,Department State University of New York at Albany July, 1976 *This research was supported in part by a SUNY Research Foundation Fellowship. , 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 [2r71* 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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 6

HOW NOT TO ESTABLISH COMPLEXITY BOUNDS
FOR THE CONTEXT FREE LAXGUAGES*

    F. D. Lewis
Technical Report 76-2

     Computer Science,Department
State University of New York at Albany

July, 1976

*This research was supported in part by a SUNY Research Foundation
Fellowship.
,

[This page contains 1 picture or other non-text object]

Page 2 of 6

      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.

[This page contains 1 picture or other non-text object]

Page 3 of 6

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
[2r71*

    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 [6] and is treated in detail in [7].

DEFINITION. The set A is many-one reducible to the set B
[denoted A B] via the function f .iff:

[This page contains 1 picture or other non-text object]

Page 4 of 6

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 [4].

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...