Space-bounded complexity classes and iterated deterministic substitution : (preprint)
P.R.J. Asveld · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1979
We investigate the effect on the space complexity when a language family K is extended by means of iterated A-free deterministic substitution to the family n(K).If each language in K is accepted by a one-way nondeterministic Tirrulti-tape Turing machine within space S(n) for some monotonicalso included in NSPACE(S(n)).An implication similar to the latter one also holds for DSPACE(S(n)).Consequently, some well-known space-bounded complexity classes such as the families of (non)deterministic context-sensitive languages, of twoway (non)deterministic nonerasing stack automaton languages, and PSPACE are AFL's closed under intersection and iterated A-free deterministic substitution.On the other hand no space-bounded complexity class which includes DPSACE(log n) is closed under controlled iterated A-free (non)deterministic substitution.