# Space-Bounded Complexity Classes and Iterated Deterministic Substitution

P.R.J. Asveld

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

### 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.
Original language English 10.1016/S0019-9958(80)90172-2 282-299 18 Information and Control 44 10.1016/S0019-9958(80)90172-2 https://doi.org/10.1016/S0019-9958(80)90172-2 Published - 1980

### Keywords

• MSC-68C25
• MSC-68F05
• HMI-SLT: Speech and Language Technology

### Cite this

Asveld, P. R. J. (1980). Space-Bounded Complexity Classes and Iterated Deterministic Substitution. Information and Control, 44(10.1016/S0019-9958(80)90172-2), 282-299. [10.1016/S0019-9958(80)90172-2]. https://doi.org/10.1016/S0019-9958(80)90172-2