Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Szepietowski A. — Turing Machines with Sublogarithmic Space
Szepietowski A. — Turing Machines with Sublogarithmic Space



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Turing Machines with Sublogarithmic Space

Автор: Szepietowski 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.


Язык: en

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: 1

Год издания: 1994

Количество страниц: 115

Добавлена в каталог: 09.02.2011

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$      8
$A - B$      7
$AB$      7
$ASPACE[L(n)]$      14
$A\cap B$      7
$A\cup B$      7
$A\subseteq B$      7
$A\varsubsetneq B$      7
$a^{*} = \{a\}^{*}$      7
$A^{*}$      7
$A^{c} = \Sigma^{*} - A$      7
$A^{n}$      7
$CSR(T)$      30
$DSPACE[L(n)]$      14
$DSPACE^{dem}[L(N)]$      109
$DSPACE^{dot}[L(N)]$      104
$DSPACE^{peb}[L(N)]$      107
$f(n) \ll g(n)$      14
$lcmA$      22
$middle$      14
$MINS_{x|y}$      32
$MINS_{x|y}(r)$      31
$NSPACE[L(n)]$      14
$NSPACE^{dem}[L(N)]$      109
$NSPACE^{dot}[L(N)]$      104
$NSPACE^{peb}[L(N)]$      107
$O(g(n))$      14
$one-way$      14
$P(G)$      70
$Pad(G, M)$      68
$SEC_{x|y}(T)$      30
$SP(T)$      30
$strong$      14
$S_{x|y}^{k}$      30
$S_{x|y}^{k}(r)$      30
$weak$      14
$x(i,j)$      100
$\cong_{k}$      84
$\equiv_{k}$      28
$\lambda$      7
$\log n$      14
$\log^{(k)}n$      14
$\log^{*}n$      14
$\mathcal{P}(A)$      7
$\omega(i)$      7
$\Pi_{k}$-alternating Turing machine      13
$\Pi_{k}-SPACE[L(n)]$      14
$\Sigma^{(2)}$      100
$\Sigma^{*}$      7
$\Sigma_{k}$-alternating Turing machine      13
$\Sigma_{k}-SPACE[L(n)]$      14
$\simeq_{k}$      108
$|\omega|$      7
1-inkdot Turing machine      104
1-pebble Turing machine      107
2-space constructible function      100
Accepting computation      10
Accepting configuration      10
Accepting state      8
Accepting subtree      30
Accepting tree      12
Accessible configuration      10
Alphabet      7
Alternating Turing machine      12
Alternation-bounded Turing machine      12
Blank symbol      8
Bounded language      7
cell      7
co-$\mathcal{C}$      7
Complement      7
Computation      10
Computation tree      12
Concatenation      7
Configuration      9
Counter      17
Demon Turing machine      109
Deterministic Turing machine      9
Difference      7
Empty word      7
Endmarker      8
Existential configuration      12
Existential state      12
Final configuration      10
Fully 2-space constructible function      100
Fully space constructible function      37
Halting Turing machine      48
Immediate successor      9
inclusion      7
Independent complement      95
Independent simulation      95
Initial configuration      9
Initial state      8
Input      8
Input head      8
Input tape      8
Input tape alphabet      8
Internal configuration      11
Intersection      7
k-equivalent      28
k-pebble automaton      16
Kleene closure      7
Language      7
Language accepted by Turing machine      10
Left endmarker      8
Length      7
letter      7
log-space reduction      19
Middle space-bounded Turing machine      13
Nondeterministic Turing machine      7
Nondeterministically fully space constructible function      37
NSPACE($\log (n)$)-complete language      19
One-way Turing machine      9
padding      68 70
Power set      7
Proper inclusion      7
Pumping lemma      22
Push-down tape      16
Recognizing Turing machine      10
Right endmarker      8
Set of states      7
Space      13
Space complexity class      14
Space constructible function      37
Space-bounded Turing machine      13
State      7
STEP      8
Strongly space-bounded Turing machine      13
Symbol      7
Tally language      7
Transducer      19
Transition function      8
Tree of accessible configurations      10
Turing machine      7
Two-dimensional tape      100
Two-dimensional Turing machine      100
union      7
Universal configuration      12
Universal state      12
Weakly space-bounded Turing machine      13
Word      7
Work head      7
Work tape      7
Work tape alphabet      8
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте