Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
<< vorige    volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 5 van 18 gevonden artikelen
  Deterministic One-Way Turing Machines with Sublinear Space
Titel: Deterministic One-Way Turing Machines with Sublinear Space
Auteur: Kutrib, Martin
Provillard, Julien
Vaszil, Gy├Ârgy
Wendlandt, Matthias
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 136 (2015) nr. 1-2 pagina's 139-155
Jaar: 2015-02-06
Inhoud: Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The class of functions space constructible by such machines is investigated, and it is shown that every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. We prove that the restricted mode coincides with the strong mode for space constructible functions. The known infinite, dense, and strict hierarchy of strong space complexity classes is derived also for the weak mode by Kolmogorov complexity arguments. Finally, closure properties under AFL operations, Boolean operations and reversal are shown.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften

                             Details van artikel 5 van 18 gevonden artikelen
<< vorige    volgende >>
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland