RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
16 мая 2017 г. 18:30, г. Москва, ГЗ МГУ, ауд. 16-04
 


Исчисления Ламбека с обогащением сигнатуры операцией итерации

С. Л. Кузнецов

Математический институт им. В.А. Стеклова Российской академии наук, г. Москва

Количество просмотров:
Эта страница:67

Аннотация: Обычное исчисление Ламбека задаёт атомарную теорию частично упорядоченных полугрупп с операциями левого и правого деления, а исчисление Ламбека с единицей — атомарную теорию частично упорядоченных моноидов с делениями. Обогащение сигнатуры операцией итерации даёт понятие алгебры Клини с делениями. Естественный пример такой алгебры - множество формальных языков, на котором заданы операции умножения, левого и правого делений и итерации Клини. В случае исчисления Ламбека без единицы рассматриваются языки без пустого слова, а вместо итерации Клини - положительная итерация.
В докладе будет представлена аксиоматизация исчисления Ламбека с итерацией, как с единицей, так и без неё, в виде секвенциальных (генценовских) исчислений. При этом используется правило вывода с бесконечным числом посылок ("омега-правило"). Для исчисления с положительной итерацией (без единицы) доказана $\Pi_1$-полнота проблемы выводимости. В частности, отсюда следует, что множество теорем этого исчисления не является рекурсивно перечислимым.
Аналогичный вопрос для исчисления Ламбека с единицей и итерацией Клини остаётся открытым.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019