Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Space-Bounded Complexity Classes and Iterated Deterministic Substitution

Share/Save/Bookmark

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

[img]
Preview
PDF
724Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/65595
Official URL:http://dx.doi.org/10.1016/S0019-9958(80)90172-2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page