Space-Bounded Complexity Classes and Iterated Deterministic Substitution


Asveld, P.R.J. (1980) Space-Bounded Complexity Classes and Iterated Deterministic Substitution. Information and Control, 44 . pp. 282-299. ISSN 0019-9958

Abstract:We investigate the effect on the space complexity when a language family $K$ is extended by means of $\lambda$-free deterministic substitution to the family $\eta(K)$. If each language in $K$ is accepted by a one-way nondeterministic multi-tape Turing-machine within space $S(n)$ for some monotonic space bound $S(n)\geq \log n$, then $\eta(K)$ is included in ${\rm NSPACE}(S(n))$. Thus for each monotonic space bound $S(n)\geq n$, the inclusion $K\subseteq{\rm NSPACE}(S(n))$ implies that $\eta(K)$ is also included in ${\rm NSPACE}(S(n))$. An implication similar to the latter one also holds for ${\rm DSPACE}(S(n))$.

Consequently, some well-known space-bounded complexity classes such as the families of (non)deterministic context-sensitive languages, of two-way (non)deterministic nonerasing stack automaton languages and $\cal PSPACE$ are AFL's closed under intersection and iterated $\lambda$-free deterministic substitution. On the other hand no complexity class which includes ${\rm DSPACE}(\log n)$ is closed under iterated $\lambda$-free (non)deterministic substitution.
Item Type:Article
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page