Ferrante J., Rackoff Ch.W. — The Computational Complexity of Logical Theories :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Ferrante J., Rackoff Ch.W. — The Computational Complexity of Logical Theories

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

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

Название: The Computational Complexity of Logical Theories

Авторы: Ferrante J., Rackoff Ch.W.

Язык:

Рубрика: Математика/

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

ed2k: ed2k stats

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

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

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

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

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

$DIST_{n}$       180
$E_{n,k}$       34
$FULL_{n}$       172
$Next_{M}$       149
$N_{k}$       8
$n{\stackrel{\equiv}{,}}k$       33
$ORD_{n}$       172
$SET_{n}$       180
$space_{M}$       12
$START_{Y}$       182
$Time_{M}$       22
$[i]_{n}$       55
$\begin{array}{c}n \\X \\k=1\end{array}A_{r}$ , $A^{n}$ , $\bar{a}_{n}$       8
$\infty$       55
$\lambda$ , word of length 0      9
$\leq_{log-lin}$ , $\leq_{\rho\ell}$       16
$\lfloor r \rfloor$ , $\lceil r \rceil$       8
$\mathbb{N}$ , $<N,+,\leq,0>$       21
$\mathbb{R}$ , $<R,+,\leq,0>$       21
$\mathbb{Z}$ , $<Z,+,\leq,0>$       21
$\pi_{J}$       8
$\stackrel{=}{n}$       55
$\thickapprox$ mod j      8
$\varnothing$ , empty set      8
$\vee$ , $\wedge$ , $\rightarrow$ , $\sim$ , $\forall$ , $\exists$       20
$\|\;\|$       30
$|A|_{\infty}$       57
(h,H) bounded      32
1-1 function      60—80
1-1 function, with a monadic predicate      81—101
1-1 function, with k monadic predicates      101 218
1-CHAINS(A)      61
2-CHAINS(A)      61
A |= $F(\bar{a}_{k})$       22
Abelian groups      137—140 146 147
acc(n)      148
Atomic formula      20
Boolean combination of subformulas      23
BRep      10
complexity      44
digit      10
Direct power, strong      144
Direct power, weak      128 141
Direct product      144
Distance from a to b (d(a,b))      63
dspace      13
DTIME      12
Ehrenfeucht games      1 28 128
F $\underline{true}$ in A (A satisfies F)      22
First order language      20
Formula      20
Formulas, equivalent      22
H-bounded      30
I, $N^{+}$ , positive integers      8

Instantaneous description, i.d.      148
Integer, addition      47 135
Integer, multiplication      135—137
Integer, order      124 200
IOTM      11
Join      112
Joins      113
k mod j      8
k-rep      10
L(M)      12
lcm A      48
Length of a word w, $\ell n(w)$       9
Lexicographical order      126 200
Linear bounded      16
log(r), $log_{2}(r)$       8
logspace      16
Loop of size n      61
LOOPS(A,j)      61
M(n,k)      38
N, nonnegative integers      8
n-word of a, W(n,a)      82
Norm of A, $\|A\|$       29
NSPACE      13
NTime      12
O(g(n)), o(g(n))      15
One sided chain      61
One successor      126 187—199
One successor, with monadic predicates      101 201—218
Origin      61
ORIGINS(A)      61
P(A), power set of A      8
P-structure      162
Pairing functions      162
Polylin      16
Prenex normal form      23
Presburger arithmetic      see "Integer" "Addition"
Q, rationals      8
q-depth (quantifier depth)      24
R, real numbers      8
Rational order      126
real addition      54
SAT(C)      22
Sentence      21
Simple Turing machine (STM)      148
TH(C)      22
Two sided chain      61
Two sided recursion of concatenation      19
Two successors      111 219—222
Two successors, with equal length      102—111 219—222
Well-order      124 200
Word      9
WORDS (A,W)      83
Z, integers      8
|A| cardinality of A      8
|k|, absolute value of k      8

О проекте