Space-Bounded Complexity Classes and Iterated Deterministic Substitution

P.R.J. Asveld

    Research output: Book/ReportReportOther research output

    Abstract

    We investigate the effect on the space complexity when a language family K is extended by means of iterated λ-free deterministic substitution to the family η(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) ⩾ log n, then η(K) is included in NSPACE(S(n)). Thus for each monotonic space bound S(n) ⩾ n, the inclusion K ⊆ NSPACE(S(n)) implies that η(K) is also 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 two-way (non)deterministic nonerasing stack automaton languages, and are AFL's closed under intersection and iterated λ-free deterministic substitution. On the other hand no complexity class which includes DSPACE(log n) is closed under controlled iterated λ-free (non) deterministic substitution.
    Original languageEnglish
    Place of PublicationAmsterdam
    PublisherStichting Mathematisch Centrum
    Number of pages21
    Publication statusPublished - 1979

      Fingerprint

    Keywords

    • (Controlled) iterated parallel rewriting
    • Space-bounded complexity classes
    • HMI-SLT: Speech and Language Technology
    • Iterated (deterministic) substitution
    • Closure properties

    Cite this

    Asveld, P. R. J. (1979). Space-Bounded Complexity Classes and Iterated Deterministic Substitution. Amsterdam: Stichting Mathematisch Centrum.