On the extension of Gladkij's Theorem and the Hierarchies of languages

✍ Scribed by Yoshihide Igarashi; Namio Honda

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 939 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80044-3

✦ Synopsis

Let T be a computable, monotonic increasing function from non-negative integers to positive integers. Then it is said that c~ _C Z* is in a class Lr if there exists a phrase structure grammar G, which generates all words of length n in c~ within length T(n) of derivations for each n. A main result of this paper is an extension of the A. V. Gladkij's Nonlinear Theorem on Context-Sensitive Grammars. Our extended theorem is as follows: Let q~ be a function defined on the set of all strings on an alphabet 27 = {at, as}, taking as values non-void subsets of 2:*. Let .L#~ be a language {xb<p(x) bx [ x ~ 27"}, where b is a symbol not in Z'. Let ~ be a function from Z'* to positive integres defined by ~(x) = min{[ xb~v(x) bx [}, and let f~0 be a function from non-negative integers to positive integers defined by f~o(n)= max{o~(x)[ x a 27", [ x ] = n}. If T is a time function such that limn~o~(T(f~(n))/n ~) = 0, then Lr does not contain s

From this result, an open problem proposed by R. V. Book are solved. Moreover from this result, it is shown that there exist infinitely long chains of distinct complexity classes between certain two distinct complexity classes.