![]() |
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Доказано, что коммуникационная сложность задачи приближения колмогоровской сложности пары слов примерно равна длине этих слов. Найдено преобразование коммуникационных протоколов с частными случайными битами в протоколы с общими случайными битами с наименьшим увеличением разглашаемой информации. Доказано, что для любого тотального алгоритма, который по любой программе слова находит список слов, содержащий почти минимальную программу для этого слова, размер списка должен быть экспоненциального от длины слова размера. Получен ряд результатов о локальной табличности и финитной аппроксимируемости полимодальных логик, в частности, произведений. Рассматривается фрагмент языка модальной логики, состоящий из импликаций A->B, где формулы A и B строятся из пропозициональных переменных и константы «истина» лишь с помощью конъюнкции и модальностей типа ромб. Такой фрагмент называем строго позитивным. Сформулировано арифметически полное исчисление с модальностями, занумерованными натуральными числами и символом омега, где омега соответствует полной равномерной схеме рефлексии в арифметике, а натуральное чимло n соответствует ограничению этой схемы арифметическими Пn+1-предложениями. Для этого исчисления установлена теорема о полноте относительно подходящего класса конечных шкал Крипке, доказана полиномиальная разрешимость проблемы выводимости, а также теорема об арифметической полноте, аналогичная известной теореме Р. Соловея для стандартной логики доказуемости. Предъявлен способ преобразования контекстно-свободной грамматики в форме Хомского в грамматику Ламбека без умножения, сохраняющий структуру деревьев разбора и семантическую разметку выводимых слов. Построены исчисления гильбертовского (несеквенциального) типа для исчисления Ламбека с двумя делениями и исчисления Ламбека с одним делением, допускающего пустые левые части секвенций.
госбюджет, раздел 0110 (для тем по госзаданию) |
# | Сроки | Название |
1 | 1 января 2014 г.-31 декабря 2014 г. | Алгоритмические и семантические вопросы математической логики |
Результаты этапа: Доказано, что коммуникационная сложность задачи приближения колмогоровской сложности пары слов примерно равна длине этих слов. Найдено преобразование коммуникационных протоколов с частными случайными битами в протоколы с общими случайными битами с наименьшим увеличением разглашаемой информации. Доказано, что для любого тотального алгоритма, который по любой программе слова находит список слов, содержащий почти минимальную программу для этого слова, размер списка должен быть экспоненциального от длины слова размера. Получен ряд результатов о локальной табличности и финитной аппроксимируемости полимодальных логик, в частности, произведений. Рассматривается фрагмент языка модальной логики, состоящий из импликаций A->B, где формулы A и B строятся из пропозициональных переменных и константы «истина» лишь с помощью конъюнкции и модальностей типа ромб. Такой фрагмент называем строго позитивным. Сформулировано арифметически полное исчисление с модальностями, занумерованными натуральными числами и символом омега, где омега соответствует полной равномерной схеме рефлексии в арифметике, а натуральное чимло n соответствует ограничению этой схемы арифметическими Пn+1-предложениями. Для этого исчисления установлена теорема о полноте относительно подходящего класса конечных шкал Крипке, доказана полиномиальная разрешимость проблемы выводимости, а также теорема об арифметической полноте, аналогичная известной теореме Р. Соловея для стандартной логики доказуемости. Предъявлен способ преобразования контекстно-свободной грамматики в форме Хомского в грамматику Ламбека без умножения, сохраняющий структуру деревьев разбора и семантическую разметку выводимых слов. Построены исчисления гильбертовского (несеквенциального) типа для исчисления Ламбека с двумя делениями и исчисления Ламбека с одним делением, допускающего пустые левые части секвенций. | ||
2 | 1 января 2015 г.-31 декабря 2015 г. | Алгоритмические и семантические вопросы математической логики |
Результаты этапа: Установлена связь между квадратами Сегерберга модальных логик и тождествами в реляционных алгебрах. Найдены достаточные условия для полноты по Крипке логики, получающейся расширением некоторой логики модальностью транзитивного замыкания. Для расширения исчисления Ламбека с помощью экспоненциальной и субэкспоненциальной (допускающей только правила сокращения и перестановки) модальностей построены исчисления генценовского типа, правильно учитывающие ламбеково ограничения на непустоту левой части секвенций. Для исчисления Ламбека, обогащённого итерацией Клини, построено инфинитарное исчисление генценовского типа и доказана полнота относительно языковых моделей его фрагмента без умножения, в котором связка "итерация" допускается только в знаменателях. Построено полное интуиционистское исчисление высказываний, использующее только эквиваленцию и конъюнкцию в качестве единственных логических связок. Проведено сравнение различных интерпретаций базисной логики предикатов. Доказано, что семантика абсолютной арифметической реализуемости и семантика. основанная на примитивно-рекурсивной реализуемости, введенной С. Салехи, не совпадают. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".