Автоматная сложность вычисления формул Кудрин, Александр Александрович

Короткий опис

Кудрин, Александр Александрович.
Автоматная сложность вычисления формул : диссертация ... кандидата физико-математических наук : 01.01.09. - Москва, 2000. - 99 с. : ил.
Оглавление диссертациикандидат физико-математических наук Кудрин, Александр Александрович
Введение
1 Автоматная сложность вычисления формул в случае базиса, состоящего из одной операторной формулы длины
1.1 Постановка задачи.
1.2 Формулировка результатов и доказательство нижних оценок
1.3 Доказательство нижних оценок.
1.4 Доказательство пункта 3 из Теоремы 2.
2 Автоматная сложность вычисления формул в случае базиса, состоящего произвольного числа операторных формул длины
2.1 Вспомогательные утверждения
2.2 Случай базиса вида F — {((xaiy)a2z),((x(3iy)(32z)}.
2.3 Случай базиса вида F = {(xa1(ya2z)), (xfti(yf32z))}.
2.4 Автоматный случай. Доказательство части б) пункта 1 Леммы 10.
2.5 Случай базиса вида F = {((xaiy)a2z), (x0i(yP2z))}.
2.6 Формулировка общей теоремы.
3 Автоматная сложность вычисления формул в случае произвольного базиса, состоящего из операторных формул
3.1 Оценка числа базисов, для которых справедлива оценка SF(ti) х п.
3.2 Обобщенная конструкция.*