Turing machines with sublogarithmic space
This comprehensive monograph investigates the computational power of Turing machines with sublogarithmic space. The studies are devoted to the Turing machine model introduced by Stearns, Hartmanis, and Lewis (1965) with a two-way read-only input tape and a separate two-way read-write work tape. The...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | Livre numérique |
| اللغة: | Anglais |
| منشور في: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| سلاسل: | Lecture notes in computer science
843 |
| الموضوعات: | |
| الوصول للمادة أونلاين: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| ملاحظة: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Turing machines with sublogarithmic space, Andrzej Szepietowski, Berlin, Springer-Verlag, 1994, 1 vol. (VIII-114 p.), Lecture notes in computer science, 0-387-58355-6 • Turing Machines with Sublogarithmic Space, Texte imprimé, 9783662192689 |
| LEADER | 03381nam a22003857a 4500 | ||
|---|---|---|---|
| 001 | 945082 | ||
| 008 | 110927q2000 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN155213814 | ||
| 020 | |a 9783540486695 (PDF) | ||
| 041 | 0 | |a eng | |
| 082 | |a 004 | ||
| 082 | |a 511.3 | ||
| 100 | 1 | |a Szepietowski, Andrzej, |d 19..- | |
| 245 | 1 | 0 | |a Turing machines with sublogarithmic space |c Andrzej Szepietowski. |
| 260 | |a Berlin [etc.] : |b Springer. | ||
| 260 | |a Cham : |b Springer Nature, |c [20..]. | ||
| 490 | 0 | |a Lecture notes in computer science |v 843 |x 1611-3349 | |
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 505 | 0 | |a Basic Notions -- Languages acceptable with logarithmic space -- Examples of languages acceptable with sublogarithmic space -- Lower bounds for accepting non-regular languages -- Space constructible functions -- Halting property and closure under complement -- Strong versus weak mode of space complexity -- Padding -- Deterministic versus nondeterministic Turing machines -- Space hierarchy -- Closure under concatenation -- Alternating hierarchy -- Independent complement -- Other models of Turing machines. | |
| 506 | |a Accès en ligne pour les établissements français bénéficiaires des licences nationales | ||
| 506 | |a Accès soumis à abonnement pour tout autre établissement | ||
| 506 | |a Conditions particulières de réutilisation pour les bénéficiaires des licences nationales. https://www.licencesnationales.fr/springer-nature-ebooks-contrat-licence-ln-2017 | ||
| 520 | |a This comprehensive monograph investigates the computational power of Turing machines with sublogarithmic space. The studies are devoted to the Turing machine model introduced by Stearns, Hartmanis, and Lewis (1965) with a two-way read-only input tape and a separate two-way read-write work tape. The book presents the key results on space complexity, also as regards the classes of languages acceptable, under the perspective of a sublogarithmic number of cells used during computation. It originates from courses given by the author at the Technical University of Gdansk and Gdansk University in 1991 and 1992. It was finalized in 1994 when the author visited Paderborn University and includes the most recent contributions to the field. | ||
| 650 | |a Informatique | ||
| 650 | |a Complexité de calcul (informatique) | ||
| 650 | |a Logique symbolique et mathématique | ||
| 650 | |a Machines de Turing | ||
| 776 | 0 | |0 020235720 |t Turing machines with sublogarithmic space |f Andrzej Szepietowski |c Berlin |n Springer-Verlag |d 1994 |p 1 vol. (VIII-114 p.) |s Lecture notes in computer science |z 0-387-58355-6 | |
| 776 | 0 | |t Turing Machines with Sublogarithmic Space |b Texte imprimé |z 9783662192689 | |
| 856 | 4 | |q PDF |u https://doi.org/10.1007/3-540-58355-6 |z Accès sur la plateforme de l'éditeur | |
| 856 | 4 | |u https://revue-sommaire.istex.fr/ark:/67375/8Q1-Z682ZXZX-7 |z Accès sur la plateforme Istex | |
| 856 | 4 | |5 452349901:747913846 |u https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.1007/3-540-58355-6 |z Accès Université d'Orléans | |
| 856 | 4 | |5 180339901:750926619 |u https://ezproxy.insa-cvl.fr/login?qurl=https://doi.org/10.1007/3-540-58355-6 |z Accès INSA CVL | |
| 997 | |0 945082 |1 Livre numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||