Сложность множества тавтологий и некоторых родственных ему множеств Ганичева, Антонина Валериановна

brief description

Ганичева, Антонина Валериановна.
Сложность множества тавтологий и некоторых родственных ему множеств : диссертация ... кандидата физико-математических наук : 01.01.06. - Калинин, 1983. - 119 с. : ил.
Оглавление диссертациикандидат физико-математических наук Ганичева, Антонина Валериановна
ВВЕДЕНИЕ.
ПЛАВА. I. Мера сложности множества тавтологий и некоторых других множеств формул.
§1. Необходимое условие ограниченности меры контекстности функцией порядка о(Сод.^п)
§2. Мера правой контекстности для множества тавтологии при двоичном кодировании
§3. Мера контекстности и мера правой контекстности для множества тавтологии при унарном кодировании Зт
§4. Сигнализирующая времени для множества тавтологий и множества выполнимых формул
ГЛАВА 2. Множества СЛист., <%илт9 (ХИ7 Ын, (Хкист,01ё«т и подклассы класса языков, распознаваемого детерминиро-ванно за полиномиальное время
§1. Хорновские тавтологии
§2; 0 принадлежности множеств формул исчисления выс- с называний классам .5Ь
ГЛАВА 3. Место множества тавтологий и родственных множеств в низших классах примитивно-рекусивных множеств
§1. Рудиментарность множества тавтологий и некоторых других множеств
§2. Изословарность .¿
§3. 5 -рудиментарность.
ГЛАВА 4. О принадлежности множеств (%$ып> ОСн, Осн и некоторых подмножеств множества б1исгп классу индексных языков
§Г. Основные определения ;.Л
§2. Структура квазисовершенных дизьюктивных нормальных форм. / А А ^
§3. Множества (Х^ у (%н > (%н - индексные языки. Ю