Szepietowski A. — Turing Machines with Sublogarithmic Space :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

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.

Язык:

Рубрика: Computer science/

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

ed2k: ed2k stats

Издание: 1

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

$      8
      7
      7
      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
      30
      14
$DSPACE^{dem}[L(N)]$       109
$DSPACE^{dot}[L(N)]$       104
$DSPACE^{peb}[L(N)]$       107
$f(n) \ll g(n)$       14
      22
      14
$MINS_{x|y}$       32
$MINS_{x|y}(r)$       31
      14
$NSPACE^{dem}[L(N)]$       109
$NSPACE^{dot}[L(N)]$       104
$NSPACE^{peb}[L(N)]$       107
      14
      14
      70
      68
$SEC_{x|y}(T)$       30
      30
      14
$S_{x|y}^{k}$       30
$S_{x|y}^{k}(r)$       30
      14
      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

О проекте