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

摘要

Let T be a computable, monotonic increasing function from non-negative integers to positive integers. Then it is said that α⊆Σ* is in a class LT if there exists a phrase structure grammar G, which generates all words of length n in α 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 Download : Download full-size image be a function defined on the set of all strings on an alphabet Σ = {a1, a2}, taking as values non-void subsets of Σ*. Let Download : Download full-size image be a language Download : Download full-size image, where b is a symbol not in Σ. Let Download : Download full-size image be a function from Σ* to positive integres defined by Download : Download full-size image, and let Download : Download full-size image be a function from non-negative integers to positive integers defined by Download : Download full-size image, Download : Download full-size image. If T is a time function such that Download : Download full-size image, then LT does not contain Download : Download full-size image. 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 betwwen certain two distinct complexity classes.