Space-Bounded Complexity Classes and Iterated Deterministic Substitution

P.R.J. Asveld

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Citations (Scopus)
    47 Downloads (Pure)


    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 languageEnglish
    Article number10.1016/S0019-9958(80)90172-2
    Pages (from-to)282-299
    Number of pages18
    JournalInformation and Control
    Issue number10.1016/S0019-9958(80)90172-2
    Publication statusPublished - 1980



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