#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
On next Monday, May 11, 18:30 Msk (17:30 Paris), our 6th year students will present their graduate Diploma papers:
1. Darya Belogortseva, Information complexity of communication protocols,
Внутреннее разглашение информационных протоколов
The talk will be in Russian
2. Gleb Volgin, Rotation protocol resilience.
The talk will be in English
3. Rustam Zyavgarov, On obstacles to materialization of the mutual information in well-mixing graphs,
О препятствиях для материализации взаимной информации в графах со свойством быстрого перемешивания.
The talk will be in Russian
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
On next Monday, May 11, 18:30 Msk (17:30 Paris), our 6th year students will present their graduate Diploma papers:
1. Darya Belogortseva, Information complexity of communication protocols,
Внутреннее разглашение информационных протоколов
The talk will be in Russian
2. Gleb Volgin, Rotation protocol resilience.
The talk will be in English
3. Rustam Zyavgarov, On obstacles to materialization of the mutual information in well-mixing graphs,
О препятствиях для материализации взаимной информации в графах со свойством быстрого перемешивания.
The talk will be in Russian
#матлог #спецсеминар #нпммвя
В четверг 14 мая в Институте языкознания РАН (с возможностью подключения онлайн) состоится состоится заседание семинара «Некоторые применения математических методов в языкознании» им. В.А. Успенского
с докладом Ксении Андреевны Студеникиной "Подходы к повышению безопасности текста, генерируемого большими языковыми моделями".
Время: 14 мая, 18:00-19:30.
Место: Институт языкознания РАН, Большой Кисловский пер., 1, стр. 1, конференц-зал. Для прохода необходимо зарегистрироваться по ссылке ниже и взять с собой паспорт.
Ссылка для регистрации: https://forms.gle/Hsc6PRBWSQx7t417A
(все зарегистрировавшиеся получат ссылку для онлайн-подключения)
Анонс:
Вместе с ростом возможностей больших языковых моделей возникает серьезная проблема: их ответы могут содержать неэтичный, предвзятый или опасный контент. Обеспечение безопасности генерируемого текста, его соответствие культурным и правовым нормам становится важным условием для использования LLM.
В докладе мы рассмотрим несколько способов, которые позволяют предотвратить генерацию вредоносных ответов:
1) Тонкая настройка с учителем (SFT) и обучение с подкреплением (RLHF) для выравнивания с намерениями человека;
2) Использование системных промптов для управления поведением модели и их уязвимость к атакам;
3) Техники машинного забывания для удаления нежелательных знаний без полного переобучения.
В докладе также будут представлены датасеты, используемые для выравнивания и стресс-тестирования моделей на предмет безопасности.
В четверг 14 мая в Институте языкознания РАН (с возможностью подключения онлайн) состоится состоится заседание семинара «Некоторые применения математических методов в языкознании» им. В.А. Успенского
с докладом Ксении Андреевны Студеникиной "Подходы к повышению безопасности текста, генерируемого большими языковыми моделями".
Время: 14 мая, 18:00-19:30.
Место: Институт языкознания РАН, Большой Кисловский пер., 1, стр. 1, конференц-зал. Для прохода необходимо зарегистрироваться по ссылке ниже и взять с собой паспорт.
Ссылка для регистрации: https://forms.gle/Hsc6PRBWSQx7t417A
(все зарегистрировавшиеся получат ссылку для онлайн-подключения)
Анонс:
Вместе с ростом возможностей больших языковых моделей возникает серьезная проблема: их ответы могут содержать неэтичный, предвзятый или опасный контент. Обеспечение безопасности генерируемого текста, его соответствие культурным и правовым нормам становится важным условием для использования LLM.
В докладе мы рассмотрим несколько способов, которые позволяют предотвратить генерацию вредоносных ответов:
1) Тонкая настройка с учителем (SFT) и обучение с подкреплением (RLHF) для выравнивания с намерениями человека;
2) Использование системных промптов для управления поведением модели и их уязвимость к атакам;
3) Техники машинного забывания для удаления нежелательных знаний без полного переобучения.
В докладе также будут представлены датасеты, используемые для выравнивания и стресс-тестирования моделей на предмет безопасности.
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 13 мая в 14:15.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Андрей Кудинов
Название: Окрестностная полнота некоторых модальных предикатных логик (продолжение)
Аннотация.
Доклад посвящен окрестностой семантике (neighbourhood semantics) для предикатных модальных логик. Хорошо известны результаты о полноте относительно окрестностных шкал с постоянными областями для логик QK и QS4. В докладе будет доказана полнота для более широкого класса логик: так называемых направленных предтранзитивных модальных предикатных логик (определение будет дано в докладе). Результаты о полноте для модальных предикатных логик остаются на данный момент довольно разрозненными и теоремы типа теоремы Салквиста пока не удается доказать. Для направленных предтранзитивных логик была известна полнота относительно шкал Крипке с расширяющимися областями. Мы покажем, что для этих логик в окрестностной семантике можно обойтись постоянными областями, при этом аксиома Баркан, которая для шкал Крипке соответствует постоянным областям, в окрестностных шкалах опровергается даже на постоянных областях.
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 13 мая в 14:15.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Андрей Кудинов
Название: Окрестностная полнота некоторых модальных предикатных логик (продолжение)
Аннотация.
Доклад посвящен окрестностой семантике (neighbourhood semantics) для предикатных модальных логик. Хорошо известны результаты о полноте относительно окрестностных шкал с постоянными областями для логик QK и QS4. В докладе будет доказана полнота для более широкого класса логик: так называемых направленных предтранзитивных модальных предикатных логик (определение будет дано в докладе). Результаты о полноте для модальных предикатных логик остаются на данный момент довольно разрозненными и теоремы типа теоремы Салквиста пока не удается доказать. Для направленных предтранзитивных логик была известна полнота относительно шкал Крипке с расширяющимися областями. Мы покажем, что для этих логик в окрестностной семантике можно обойтись постоянными областями, при этом аксиома Баркан, которая для шкал Крипке соответствует постоянным областям, в окрестностных шкалах опровергается даже на постоянных областях.
#матлог #учёба #спецсеминар
На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ
"Модальная и алгебраическая логика" и "Логические методы в информатике"
в четверг 14.05, начало в 18:30, состоится доклад
Слюсарев Владислав Владимирович (МФТИ)
Две конструкции случайной шкалы Крипке
Мы изучаем вероятности общезначимости модальных формул в случайных шкалах Крипке на фиксированном n-элементном множестве. Распределение случайной n-элементной шкалы для каждого n может быть выбрано разными способами и приводит к разным результатам. Фиксируя распределение для каждого n, мы получаем семейство случайных шкал. Если для данной формулы вероятность того, что она общезначима в случайной n-элементной шкале, стремится к единице при n→∞, то мы говорим, что эта формула общезначима асимптотически почти наверное в данном семействе случайных шкал. Множество формул, общезначимых асимптотически почти наверное, называется почти достоверной логикой семейства случайных шкал. Мы говорим, что семейство случайных шкал удовлетворяет закону нуля и единицы, если вероятность общезначимости любой модальной формулы стремится либо к 0, либо к 1 при n→∞.
Наиболее естественным будет рассмотреть равномерное распределение на множестве всех шкал Крипке на n точках. Ж.-М. Ле Барс опроверг закон нуля и единицы для этого семейства [1]. В. Горанко описал частичную счётную аксиоматизацию для его почти достоверной логики [2]. Неизвестно, является ли эта логика разрешимо аксиоматизируемой. Позитивные результаты были получены для семейства случайных шкал с равномерным распределением на всех n-элементных шкалах логики GL: Р. Вербрюгге доказала закон нуля и единицы и описала счётную аксиоматизацию почти достоверной логики [3].
В этом докладе мы рассмотрим две общих конструкции случайных шкал Крипке. В первой конструкции рассматривается равномерное распределение на множестве всех n-элементных шкал заданной модальной логики L. Мы показываем, что для довольно широкого семейства логик вероятность общезначимости формулы можно оценить, рассматривая связные шкалы логики L, которые имеют более простую комбинаторную структуру. С помощью этого результата мы получаем конечные аксиоматизации почти достоверных логик, соответствующих логикам SL, GL.3, Grz.3, KD5, KD45, K5B и S5, и доказываем закон нуля и единицы для KD5, KD45, K5B и S5 [4,5].
Во второй конструкции мы рассматриваем Хорнову модальную логику L и строим L-замыкание случайной шкалы с равномерным распределением среди всех n-элементных шкал. Мы доказываем, что почти достоверные логики таких семейств случайных шкал являются нормальными расширениями логики, заданной аксиомами Горанко. Далее мы рассматриваем хорновы логики вида K + ♢^m p → ♢p и K + ♢^m □p → □^m p и доказываем, что для них выполнен закон нуля и единицы, а почти достоверная логика равна S5 [6].
[1] Le Bars J.-M. The 0-1 law fails for frame satisfiability of propositional modal logic // Proceedings 17th Annual IEEE Symposium on Logic in Computer Science. — 02/2002. — P. 225–234.
[2] Goranko V. The Modal Logic of Almost Sure Frame Validities in the Finite // Advances in Modal Logic. — 2020.
[3] Verbrugge R. Zero-one laws for provability logic: Axiomatizing validity in almost all models and almost all frames // 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. — IEEE Xplore, 06/2021.
[4] Слюсарев В. В. Почти достоверная модальная логика шкал Крипке с функциональным отношением // Труды Московского физико-технического института (национального исследовательского университета). — 2024. — Т. 16,No 3 (63). — С. 57—71.
[5] Слюсарев В. В. Почти достоверные модальные логики и законы нуля и единицы в хорновых классах // Доклады РАН. Математика, информатика, процессы управления. — 2024. — Т. 519. — С. 57––64.
[6] Sliusarev V. Modal logics of almost-sure validities in some classes of Euclidean and transitive frames // Combinatorics and number theory. — 2025. — Т. 14, No 1. — С. 49––64.
Видеозаписи предыдущих
На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ
"Модальная и алгебраическая логика" и "Логические методы в информатике"
в четверг 14.05, начало в 18:30, состоится доклад
Слюсарев Владислав Владимирович (МФТИ)
Две конструкции случайной шкалы Крипке
Мы изучаем вероятности общезначимости модальных формул в случайных шкалах Крипке на фиксированном n-элементном множестве. Распределение случайной n-элементной шкалы для каждого n может быть выбрано разными способами и приводит к разным результатам. Фиксируя распределение для каждого n, мы получаем семейство случайных шкал. Если для данной формулы вероятность того, что она общезначима в случайной n-элементной шкале, стремится к единице при n→∞, то мы говорим, что эта формула общезначима асимптотически почти наверное в данном семействе случайных шкал. Множество формул, общезначимых асимптотически почти наверное, называется почти достоверной логикой семейства случайных шкал. Мы говорим, что семейство случайных шкал удовлетворяет закону нуля и единицы, если вероятность общезначимости любой модальной формулы стремится либо к 0, либо к 1 при n→∞.
Наиболее естественным будет рассмотреть равномерное распределение на множестве всех шкал Крипке на n точках. Ж.-М. Ле Барс опроверг закон нуля и единицы для этого семейства [1]. В. Горанко описал частичную счётную аксиоматизацию для его почти достоверной логики [2]. Неизвестно, является ли эта логика разрешимо аксиоматизируемой. Позитивные результаты были получены для семейства случайных шкал с равномерным распределением на всех n-элементных шкалах логики GL: Р. Вербрюгге доказала закон нуля и единицы и описала счётную аксиоматизацию почти достоверной логики [3].
В этом докладе мы рассмотрим две общих конструкции случайных шкал Крипке. В первой конструкции рассматривается равномерное распределение на множестве всех n-элементных шкал заданной модальной логики L. Мы показываем, что для довольно широкого семейства логик вероятность общезначимости формулы можно оценить, рассматривая связные шкалы логики L, которые имеют более простую комбинаторную структуру. С помощью этого результата мы получаем конечные аксиоматизации почти достоверных логик, соответствующих логикам SL, GL.3, Grz.3, KD5, KD45, K5B и S5, и доказываем закон нуля и единицы для KD5, KD45, K5B и S5 [4,5].
Во второй конструкции мы рассматриваем Хорнову модальную логику L и строим L-замыкание случайной шкалы с равномерным распределением среди всех n-элементных шкал. Мы доказываем, что почти достоверные логики таких семейств случайных шкал являются нормальными расширениями логики, заданной аксиомами Горанко. Далее мы рассматриваем хорновы логики вида K + ♢^m p → ♢p и K + ♢^m □p → □^m p и доказываем, что для них выполнен закон нуля и единицы, а почти достоверная логика равна S5 [6].
[1] Le Bars J.-M. The 0-1 law fails for frame satisfiability of propositional modal logic // Proceedings 17th Annual IEEE Symposium on Logic in Computer Science. — 02/2002. — P. 225–234.
[2] Goranko V. The Modal Logic of Almost Sure Frame Validities in the Finite // Advances in Modal Logic. — 2020.
[3] Verbrugge R. Zero-one laws for provability logic: Axiomatizing validity in almost all models and almost all frames // 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. — IEEE Xplore, 06/2021.
[4] Слюсарев В. В. Почти достоверная модальная логика шкал Крипке с функциональным отношением // Труды Московского физико-технического института (национального исследовательского университета). — 2024. — Т. 16,No 3 (63). — С. 57—71.
[5] Слюсарев В. В. Почти достоверные модальные логики и законы нуля и единицы в хорновых классах // Доклады РАН. Математика, информатика, процессы управления. — 2024. — Т. 519. — С. 57––64.
[6] Sliusarev V. Modal logics of almost-sure validities in some classes of Euclidean and transitive frames // Combinatorics and number theory. — 2025. — Т. 14, No 1. — С. 49––64.
Видеозаписи предыдущих
🔥1
докладов:
https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX
Веб-страница с аннотациями и слайдами:
logic.math.msu.ru/sem/ml/
Для получения ссылки Zoom пишите на почту lev_135@mail.ru.
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!
https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX
Веб-страница с аннотациями и слайдами:
logic.math.msu.ru/sem/ml/
Для получения ссылки Zoom пишите на почту lev_135@mail.ru.
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 15.05.2026 в 16:20
Докладчик:
Николай Плетнев
Тема:
Выводимость как осмысленная стратегия: игровая семантика интуиционистской логики по Межирову
Аннотация:
В докладе рассматривается игровая семантика для интуиционистского пропозиционального исчисления, предложенная И. Межировым. Выводимость формулы в IPC отождествляется с наличием выигрышной стратегии у пропонента в игре на множестве подформул. Приводятся доказательства теорем корректности и полноты, опирающиеся на конечные модели Крипке. На примерах показывается, как стратегический выбор ходов отражает синтаксическую выводимость или строит контрпримеры. Отмечаются педагогические преимущества подхода и перспективы его применения в автоматизации доказательств.
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 15.05.2026 в 16:20
Докладчик:
Николай Плетнев
Тема:
Выводимость как осмысленная стратегия: игровая семантика интуиционистской логики по Межирову
Аннотация:
В докладе рассматривается игровая семантика для интуиционистского пропозиционального исчисления, предложенная И. Межировым. Выводимость формулы в IPC отождествляется с наличием выигрышной стратегии у пропонента в игре на множестве подформул. Приводятся доказательства теорем корректности и полноты, опирающиеся на конечные модели Крипке. На примерах показывается, как стратегический выбор ходов отражает синтаксическую выводимость или строит контрпримеры. Отмечаются педагогические преимущества подхода и перспективы его применения в автоматизации доказательств.
#матлог #наука #конференция
17-22 августа 2026 в Казани пройдёт VI Конференция математических центров России (https://mathcenter.kpfu.ru/mc-conf). На конференции традиционно будет секция «Математическая логика и теоретическая информатика», организаторы секций в этом году — Н. А. Баженов (НГУ), И. Ш. Калимуллин (КФУ) и С. Л. Кузнецов (МИАН).
Подать заявку для участия в работе секции (с докладом) можно на сайте конференции. Прямая ссылка на форму регистрации: https://forms.yandex.ru/u/6989eb021f1eb5cea44fbbe6/
Крайний срок подачи заявок — 1 июня. (После этой даты заявить доклад будет невозможно.)
По всем вопросам по поводу секции можно обращаться к её организаторам.
17-22 августа 2026 в Казани пройдёт VI Конференция математических центров России (https://mathcenter.kpfu.ru/mc-conf). На конференции традиционно будет секция «Математическая логика и теоретическая информатика», организаторы секций в этом году — Н. А. Баженов (НГУ), И. Ш. Калимуллин (КФУ) и С. Л. Кузнецов (МИАН).
Подать заявку для участия в работе секции (с докладом) можно на сайте конференции. Прямая ссылка на форму регистрации: https://forms.yandex.ru/u/6989eb021f1eb5cea44fbbe6/
Крайний срок подачи заявок — 1 июня. (После этой даты заявить доклад будет невозможно.)
По всем вопросам по поводу секции можно обращаться к её организаторам.
#матлог #учёба #просеминар
💥В пятницу 15 мая состоится очередное занятие просеминара по математической логике и информатике.
✨Тема: Булевы алгебры, продолжение: Ультрафильтры
(А.А.Запрягаев)
✨Аннотация. Мы продолжим изучать булевы алгебры и докажем при помощи ультрафильтров, что всякая булева алгебра вкладывается в некоторую алгебру множеств.
✨ Можно заранее порешать задачи (прикреплены к посту).
✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ.
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
✅Ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар.
📝 Proseminar-Stone.pdf
💥В пятницу 15 мая состоится очередное занятие просеминара по математической логике и информатике.
✨Тема: Булевы алгебры, продолжение: Ультрафильтры
(А.А.Запрягаев)
✨Аннотация. Мы продолжим изучать булевы алгебры и докажем при помощи ультрафильтров, что всякая булева алгебра вкладывается в некоторую алгебру множеств.
✨ Можно заранее порешать задачи (прикреплены к посту).
✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ.
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
✅Ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар.
📝 Proseminar-Stone.pdf
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), ауд. 313 + Kontur Talk
18.05.2026, совместное заседание с семинаром С. И. Адяна
А. Л. Таламбуца (МИАН, https://www.mathnet.ru/person20324): О проблеме равенства в минимально бесконечных группах – II (очный доклад)
В докладе будет рассматриваться проблема равенства для рекурсивных заданий минимально бесконечных групп. В первой части (16.03.2026, https://www.mathnet.ru/present49509) было установлено, что для конечно-порождённых групп этого класса проблема равенства алгоритмически разрешима. Теперь будут рассматриваться задания со счётным множеством порождающих. Будет показано, что проблема равенства разрешима для групп, которые не являются локально конечными (т.е. в которых есть конечное множество, порождающее бесконечную подгруппу). Для локально конечных минимально бесконечных групп разрешимость проблемы равенства оказывается зависимой от задания группы и оказывается эквивалентной существованию алгоритма, перечисляющего бесконечное множество слов, задающих различные элементы данной группы.
Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), ауд. 313 + Kontur Talk
18.05.2026, совместное заседание с семинаром С. И. Адяна
А. Л. Таламбуца (МИАН, https://www.mathnet.ru/person20324): О проблеме равенства в минимально бесконечных группах – II (очный доклад)
В докладе будет рассматриваться проблема равенства для рекурсивных заданий минимально бесконечных групп. В первой части (16.03.2026, https://www.mathnet.ru/present49509) было установлено, что для конечно-порождённых групп этого класса проблема равенства алгоритмически разрешима. Теперь будут рассматриваться задания со счётным множеством порождающих. Будет показано, что проблема равенства разрешима для групп, которые не являются локально конечными (т.е. в которых есть конечное множество, порождающее бесконечную подгруппу). Для локально конечных минимально бесконечных групп разрешимость проблемы равенства оказывается зависимой от задания группы и оказывается эквивалентной существованию алгоритма, перечисляющего бесконечное множество слов, задающих различные элементы данной группы.
#матлог #учёба #спецсеминар
20 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
В.Е. Карпов (МФТИ)
О $\Pi^1_1$-полноте $\Sigma_2$-теории натуральных чисел со стандартным порядком и свободной эквивалентностью
Аннотация:
Обозначим через LEq класс всех пар, состоящих из линейного порядка и эквивалентности на общем носителе. Этот класс и его подклассы играют важную роль в изучении алгоритмических свойств элементарных теорий. Нас будет интересовать естественный подкласс LEq*, состоящий из структур на натуральных числах, в которых порядок интерпретируется стандартным образом, а эквивалентность остаётся «свободной». Нетрудно видеть, что \Pi_2-теория LEq* является разрешимой. Вместе с тем будет доказано, что \Sigma_2-теория LEq* является \Pi^1_1-полной (для сравнения \Sigma_2-теория LEq является лишь \Sigma^0_1-полной).
Для доказательства желаемого результата о \Pi^1_1-полноте будет использоваться тот факт (встречающийся в работе Д. Хареля, А. Пнуэли и Дж. Стави), что множество всех кодов рекурректных недетерминированных машин Тьюринга является \Sigma^1_1-полным. Здесь прилагательное «рекуррентный» означает, что при запуске на пустой ленте у данной машины существует бесконечное вычисление, в ходе которого начальное состояние посещается бесконечно часто.
20 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
В.Е. Карпов (МФТИ)
О $\Pi^1_1$-полноте $\Sigma_2$-теории натуральных чисел со стандартным порядком и свободной эквивалентностью
Аннотация:
Обозначим через LEq класс всех пар, состоящих из линейного порядка и эквивалентности на общем носителе. Этот класс и его подклассы играют важную роль в изучении алгоритмических свойств элементарных теорий. Нас будет интересовать естественный подкласс LEq*, состоящий из структур на натуральных числах, в которых порядок интерпретируется стандартным образом, а эквивалентность остаётся «свободной». Нетрудно видеть, что \Pi_2-теория LEq* является разрешимой. Вместе с тем будет доказано, что \Sigma_2-теория LEq* является \Pi^1_1-полной (для сравнения \Sigma_2-теория LEq является лишь \Sigma^0_1-полной).
Для доказательства желаемого результата о \Pi^1_1-полноте будет использоваться тот факт (встречающийся в работе Д. Хареля, А. Пнуэли и Дж. Стави), что множество всех кодов рекурректных недетерминированных машин Тьюринга является \Sigma^1_1-полным. Здесь прилагательное «рекуррентный» означает, что при запуске на пустой ленте у данной машины существует бесконечное вычисление, в ходе которого начальное состояние посещается бесконечно часто.
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Monday, 18 May, 18:30 MSK
We have a talk of Przemysław Wałęga (Oxford), who will explain the classical "Tarski preservation theorem", which says that first-order formulas that preserve their value under taking substructures (e.g., like the formula defining a partial order) are precisely formulas that are equivalent to universal formulas. Additionally, the plan is to discuss what happens with all these in the modal logic.
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Monday, 18 May, 18:30 MSK
We have a talk of Przemysław Wałęga (Oxford), who will explain the classical "Tarski preservation theorem", which says that first-order formulas that preserve their value under taking substructures (e.g., like the formula defining a partial order) are precisely formulas that are equivalent to universal formulas. Additionally, the plan is to discuss what happens with all these in the modal logic.
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 20 мая в 14:15.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Михаил Рыбаков
Тема:
Сложность логик S1–S8 и их фрагментов.
Аннотация:
Нормальные модальные пропозициональные логики часто PSPACE-трудны (Р.Ладнер и др.), и даже при малом числе переменных в языке. В то же время все расширения таких логик, как K5 или Grz.3, являются coNP-полными. Похожая ситуация наблюдается с ненормальными логиками, содержащимися в K: логики E, EM, EN и многие другие coNP-полны (М.Варди), и то же самое справедливо для их фрагментов от малого числа переменных (А.Кудинов, М.Рыбаков).
Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 20 мая в 14:15.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Михаил Рыбаков
Тема:
Сложность логик S1–S8 и их фрагментов.
Аннотация:
Нормальные модальные пропозициональные логики часто PSPACE-трудны (Р.Ладнер и др.), и даже при малом числе переменных в языке. В то же время все расширения таких логик, как K5 или Grz.3, являются coNP-полными. Похожая ситуация наблюдается с ненормальными логиками, содержащимися в K: логики E, EM, EN и многие другие coNP-полны (М.Варди), и то же самое справедливо для их фрагментов от малого числа переменных (А.Кудинов, М.Рыбаков).
Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.
#матлог #учёба #спецсеминар
20 мая в 18:10 состоится заседание теоретического семинара «Формальная философия»
Тема доклада: Сфера действия модальности и отрицания в семантике (и в синтаксисе) русских сложных предложений.
Докладчик: А.Б. Летучий (НИУ ВШЭ).
Аннотация: Понятие сферы действия широко используется в лингвистике, причём в самых разных областях . С одной стороны, оно важно для синтаксического анализа - синтаксисты анализируют, на какие части предложения распространяется формальное влияние главного глагола или каких-либо операторов. С другой стороны, оно первостепенно важно для семантики: анализируя значение предложения, невозможно обойтись без учёта сферы действия модальных операторов или отрицания. Например, в предложении появляется единица, выражающая ирреальность - на всё ли предложение или только на его часть это ирреальное значение распространяется?
В докладе я расскажу о своих недавних и продолжающихся исследованиях, связанных со сферой действия. Например, будут рассмотрены такие предложения (примеры из корпуса и интернета):
Психолог должен помочь тем, что найдет источник травмы.
Мы не поможем автору тем, что начнём его критиковать.
В этих сложных предложениях есть показатели, снижающие реальность ситуации: в первом случае показатель должен делает ситуацию гипотетической (но ещё не реализованной, 'должен помочь, но пока не помог'), во второй показатель не просто отрицает ситуацию ('неверно, что мы поможем автору'. А вот распространяется ли действие этих операторов на вторую, зависимую часть предложения? Относится ли модальный показатель должен ещё и к части найдёт источник травмы? Отрицает ли не зависимую часть начнём его критиковать?
Ответ на эти вопросы может быть разным. Я покажу, что семантическая сфера действия показателей зависит от нескольких факторов и не всегда жёстко задана, а потом расскажу о том, как она влияет на формальные особенности некоторых предложений.
_________________
Ждём вас в кабинете А-117 или в Zoom!
Анонс и регистрация: https://llfp.hse.ru/announcements/1159272518.html
20 мая в 18:10 состоится заседание теоретического семинара «Формальная философия»
Тема доклада: Сфера действия модальности и отрицания в семантике (и в синтаксисе) русских сложных предложений.
Докладчик: А.Б. Летучий (НИУ ВШЭ).
Аннотация: Понятие сферы действия широко используется в лингвистике, причём в самых разных областях . С одной стороны, оно важно для синтаксического анализа - синтаксисты анализируют, на какие части предложения распространяется формальное влияние главного глагола или каких-либо операторов. С другой стороны, оно первостепенно важно для семантики: анализируя значение предложения, невозможно обойтись без учёта сферы действия модальных операторов или отрицания. Например, в предложении появляется единица, выражающая ирреальность - на всё ли предложение или только на его часть это ирреальное значение распространяется?
В докладе я расскажу о своих недавних и продолжающихся исследованиях, связанных со сферой действия. Например, будут рассмотрены такие предложения (примеры из корпуса и интернета):
Психолог должен помочь тем, что найдет источник травмы.
Мы не поможем автору тем, что начнём его критиковать.
В этих сложных предложениях есть показатели, снижающие реальность ситуации: в первом случае показатель должен делает ситуацию гипотетической (но ещё не реализованной, 'должен помочь, но пока не помог'), во второй показатель не просто отрицает ситуацию ('неверно, что мы поможем автору'. А вот распространяется ли действие этих операторов на вторую, зависимую часть предложения? Относится ли модальный показатель должен ещё и к части найдёт источник травмы? Отрицает ли не зависимую часть начнём его критиковать?
Ответ на эти вопросы может быть разным. Я покажу, что семантическая сфера действия показателей зависит от нескольких факторов и не всегда жёстко задана, а потом расскажу о том, как она влияет на формальные особенности некоторых предложений.
_________________
Ждём вас в кабинете А-117 или в Zoom!
Анонс и регистрация: https://llfp.hse.ru/announcements/1159272518.html
#матлог #отмены
Уважаемые коллеги, в связи с накладкой на другие лекции мы переносим доклад Михаила Рыбакова (https://t.me/msu_mathlog/504) на 27 мая.
Для информации: вот какие лекции будут проходить в ВШМ в это время:
Zhiyu Tian (Beijing International Center for Mathematical Research) и М.З. Ровинский (ВШЭ) прочитают
в рамках проекта на базе ВШМ мини-курс лекций "Geometry and Arithmetic of One-Cycles".
Лекции будут проходить 17-20 мая в аудитории 322 АдмК.
Zhiyu Tian 14:00-15:30
М.З. Ровинский 16:00-17:30
Форма для регистрации: https://forms.gle/oVta1zXC1HaiqoM89
Проект реализуется при поддержке Фонда Целевого Капитала МФТИ
https://t.me/miptfund
В канале t.me/mipt_dlipm выложены прошедшие лекции.
Уважаемые коллеги, в связи с накладкой на другие лекции мы переносим доклад Михаила Рыбакова (https://t.me/msu_mathlog/504) на 27 мая.
Для информации: вот какие лекции будут проходить в ВШМ в это время:
Zhiyu Tian (Beijing International Center for Mathematical Research) и М.З. Ровинский (ВШЭ) прочитают
в рамках проекта на базе ВШМ мини-курс лекций "Geometry and Arithmetic of One-Cycles".
Лекции будут проходить 17-20 мая в аудитории 322 АдмК.
Zhiyu Tian 14:00-15:30
М.З. Ровинский 16:00-17:30
Форма для регистрации: https://forms.gle/oVta1zXC1HaiqoM89
Проект реализуется при поддержке Фонда Целевого Капитала МФТИ
https://t.me/miptfund
В канале t.me/mipt_dlipm выложены прошедшие лекции.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 22.05.2026 в 16:20
Докладчик:
Иван Пыльцын
Название доклада:
Игровая семантика Межирова для логики Гёделя-Лёба
Аннотация:
Игровая семантика Межирова была изложена Ильёй Межировым в 2006 году для модальной логики Гжегорчика (Grz) и интуиционистской пропозициональной логики (Int), представляя из себя независимый (в частности, не опирающийся на модели Крипке) семантический подход к описанию этих логик.
Одним из естественных направлений развития игровой семантики является её перенос на другие логики. Например, в 2021 году Александра Павлова построила аналоги семантики Межирова для минимальной пропозициональной логики (MPC), логики функциональных шкал (KD!) и логики сериальных шкал (KD).
На докладе я представлю вариант игры Межирова для модальной логики Гёделя-Лёба (GL).
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 22.05.2026 в 16:20
Докладчик:
Иван Пыльцын
Название доклада:
Игровая семантика Межирова для логики Гёделя-Лёба
Аннотация:
Игровая семантика Межирова была изложена Ильёй Межировым в 2006 году для модальной логики Гжегорчика (Grz) и интуиционистской пропозициональной логики (Int), представляя из себя независимый (в частности, не опирающийся на модели Крипке) семантический подход к описанию этих логик.
Одним из естественных направлений развития игровой семантики является её перенос на другие логики. Например, в 2021 году Александра Павлова построила аналоги семантики Межирова для минимальной пропозициональной логики (MPC), логики функциональных шкал (KD!) и логики сериальных шкал (KD).
На докладе я представлю вариант игры Межирова для модальной логики Гёделя-Лёба (GL).
#матлог #учёба #просеминар
💥В пятницу 22 мая состоится очередное занятие просеминара по математической логике и информатике. Это последнее занятие в 2025-2026 учебном году.
✨Тема: Клеточные автоматы (Дмитрий Баженов, студент кафедры)
✨Аннотация. Клеточные автоматы представляют собой дискретную систему, меняющуюся с течением времени по локальным правилам: состояние клетки в следующий момент зависит от состояния её самой и её ближайших соседей. Несмотря на простоту модели, клеточные автоматы могут демонстрировать сложное поведение и являются универсальной вычислительной моделью.
✨ Можно заранее порешать задачи (прикреплены к посту).
✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ.
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
✅Ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар.
📝 klet2025.pdf
💥В пятницу 22 мая состоится очередное занятие просеминара по математической логике и информатике. Это последнее занятие в 2025-2026 учебном году.
✨Тема: Клеточные автоматы (Дмитрий Баженов, студент кафедры)
✨Аннотация. Клеточные автоматы представляют собой дискретную систему, меняющуюся с течением времени по локальным правилам: состояние клетки в следующий момент зависит от состояния её самой и её ближайших соседей. Несмотря на простоту модели, клеточные автоматы могут демонстрировать сложное поведение и являются универсальной вычислительной моделью.
✨ Можно заранее порешать задачи (прикреплены к посту).
✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ.
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
✅Ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар.
📝 klet2025.pdf
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
❤1
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), Kontur Talk
25.05.2026 Simon Santschi (https://sisantschi.github.io/), Niels Vooijs (University of Bern, https://vooijs.pages.dev/academic/):
Interpolation above S4: completing Maksimova's classification (online talk)
A logic has Craig interpolation if for every valid implication "ϕ implies ψ", there exists an interpolant χ, using only variables that occur in both ϕ and ψ, such that "ϕ implies χ" and "χ implies ψ". Maksimova showed that at most 37 normal extensions of modal S4 have Craig interpolation. For the majority of these, Craig interpolation is known. However, for six cases this remained open. We complete Maksimova's classification by proving Craig Interpolation for these. The proof builds upon the standard Smoryński model construction, but employs a novel approach using Fine's frame formulas for splitting clusters.
Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), Kontur Talk
25.05.2026 Simon Santschi (https://sisantschi.github.io/), Niels Vooijs (University of Bern, https://vooijs.pages.dev/academic/):
Interpolation above S4: completing Maksimova's classification (online talk)
A logic has Craig interpolation if for every valid implication "ϕ implies ψ", there exists an interpolant χ, using only variables that occur in both ϕ and ψ, such that "ϕ implies χ" and "χ implies ψ". Maksimova showed that at most 37 normal extensions of modal S4 have Craig interpolation. For the majority of these, Craig interpolation is known. However, for six cases this remained open. We complete Maksimova's classification by proving Craig Interpolation for these. The proof builds upon the standard Smoryński model construction, but employs a novel approach using Fine's frame formulas for splitting clusters.
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Monday, 25 May, 18:30 MSK
Speaker: Donald Stull
Title: The Dimension Spectrum of Lines in R^2.
Abstract: In this talk, we discuss the dimension spectrum of planar lines, that is, the set of possible values of the effective dimension of points on a line. We will discuss the proof that, for every planar line L, the dimension spectrum of L contains a unit interval. The starting point of this proof is the technique of N. Lutz and Stull, which was also used to prove sharp bounds of certain Furstenberg sets.
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Monday, 25 May, 18:30 MSK
Speaker: Donald Stull
Title: The Dimension Spectrum of Lines in R^2.
Abstract: In this talk, we discuss the dimension spectrum of planar lines, that is, the set of possible values of the effective dimension of points on a line. We will discuss the proof that, for every planar line L, the dimension spectrum of L contains a unit interval. The starting point of this proof is the technique of N. Lutz and Stull, which was also used to prove sharp bounds of certain Furstenberg sets.
#матлог #учёба #спецсеминар
27 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
Л. Д. Беклемишев
Пространства Плотта и монотонная логика Гёделя–Лёба
Аннотация:
В. И. Данилов обнаружил связь между топологической семантикой логики Гёделя–Лёба и структурами, возникшими в 1960-х годах в теории рационального выбора, так называемыми функциями выбора Плотта. В дальнейшем оказалось, что фактически в этой теории речь идет об окрестностных моделях субнормальной модальной логики mGL, которая расширяет логику высказываний правилом монотонности (из A→B выводится □A→□B) и стандартной аксиомой Лёба. В докладе будет рассказано о свойствах этой логики, её моделях, связи с функциями выбора и о других результатах в этом направлении, полученных в последнее время — вместе и по отдельности — В. И. Даниловым, Д. С. Шамкановым, Д. Трофимовым и докладчиком.
27 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
Л. Д. Беклемишев
Пространства Плотта и монотонная логика Гёделя–Лёба
Аннотация:
В. И. Данилов обнаружил связь между топологической семантикой логики Гёделя–Лёба и структурами, возникшими в 1960-х годах в теории рационального выбора, так называемыми функциями выбора Плотта. В дальнейшем оказалось, что фактически в этой теории речь идет об окрестностных моделях субнормальной модальной логики mGL, которая расширяет логику высказываний правилом монотонности (из A→B выводится □A→□B) и стандартной аксиомой Лёба. В докладе будет рассказано о свойствах этой логики, её моделях, связи с функциями выбора и о других результатах в этом направлении, полученных в последнее время — вместе и по отдельности — В. И. Даниловым, Д. С. Шамкановым, Д. Трофимовым и докладчиком.
👍2
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
❗Время поменялось❗
Семинар пройдет в среду 27 апреля в 13:00.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Михаил Рыбаков
Тема:
Сложность логик S1–S8 и их фрагментов.
Аннотация:
Нормальные модальные пропозициональные логики часто PSPACE-трудны (Р.Ладнер и др.), и даже при малом числе переменных в языке. В то же время все расширения таких логик как K5 или Grz.3 являются coNP-полными. Похожая ситуация наблюдается с ненормальными логиками, содержащимися в K: логики E, EM, EN и многие другие coNP-полны (М.Варди), и то же самое справедливо для их фрагментов от малого числа переменных (А.Кудинов, М.Рыбаков).
Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
❗Время поменялось❗
Семинар пройдет в среду 27 апреля в 13:00.
Адрес:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com
Докладчик: Михаил Рыбаков
Тема:
Сложность логик S1–S8 и их фрагментов.
Аннотация:
Нормальные модальные пропозициональные логики часто PSPACE-трудны (Р.Ладнер и др.), и даже при малом числе переменных в языке. В то же время все расширения таких логик как K5 или Grz.3 являются coNP-полными. Похожая ситуация наблюдается с ненормальными логиками, содержащимися в K: логики E, EM, EN и многие другие coNP-полны (М.Варди), и то же самое справедливо для их фрагментов от малого числа переменных (А.Кудинов, М.Рыбаков).
Будет рассмотрен вопрос сложности систем S1–S8 (Льюис, Лэндфорд и др.). Две из них — S4 и S5 — являются нормальными и их сложность известна. Остальные являются ненормальными, и похоже, что вопрос их сложности не исследовался. Гипотеза автора состоит в том, что и они, и их фрагменты от одной переменной (а иногда и константные фрагменты) PSPACE-трудны. Почти для всех указанных логик эту гипотезу удалось обосновать. Предполагается представить синтаксическое и семантическое описание этих логик, а также обсудить идеи, лежащие в основе полученных доказательств.
#матлог #спецсеминар #нпммвя
В четверг 28 мая в Институте языкознания РАН (с возможностью подключения онлайн) состоится состоится заседание семинара «Некоторые применения математических методов в языкознании» им. В.А. Успенского
с докладом Ани Шатских (МГУ) "Автоматическая морфологическая классификация для осетинского языка".
(перенос не состоявшегося ранее доклада)
Время: 28.05.2026, 18:00-19:30.
Место: Математический институт им. В.А. Стеклова РАН, ул. Губкина, д. 8, ауд. 104. Для прохода потребуется студенческий/пропуск любой образовательной или научной организации либо паспорт.
Ссылка для регистрации: https://forms.gle/JHdnkn9ApytBRV8ZA
(все зарегистрировавшиеся получат ссылку для онлайн-подключения; указавшие очное участие будут внесены в список на проход)
Анонс:
Доклад посвящён созданию датасета и нейросетевой модели для автоматической морфологической классификации в осетинском языке. Осетинский язык – иранский язык индоевропейской семьи, распространённый на Северном Кавказе. Этот язык является родным для по меньшей мере 550 тыс. человек и обладает долгой письменной традицией: так, литературный корпус осетинского языка содержит около 12 млн словоупотреблений. Тем не менее, до недавнего времени для осетинского языка не существовало инструментов контекстной морфологической классификации. Эта задача состоит в определении для словоформы её части речи и грамматических признаков (таких как число или падеж) с учётом контекста и является незаменимым уровнем разметки языковых корпусов.
В докладе будет описано создание обучающего корпуса с морфологической аннотацией в системе Universal Dependencies версии 2 (Nivre и др., 2020). Будут рассмотрены вызовы, которые типологические особенности осетинского ставят перед универсальными конвенциями аннотации, и расширения системы UD, принятые в ответ на них. Наконец, будет представлена первая в истории языковая модель архитектуры BERT (Devlin и др., 2019) для осетинского языка и морфологический классификатор на её основе, а также результаты экспериментов, проведённых в ходе создания и улучшения этих моделей.
Литература:
1. Devlin, Jacob и др. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. URL: https://arxiv.org/abs/1810.04805v2
2. Nivre, Joakim и др. (2020). Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection. URL: https://arxiv.org/abs/2004.10643
В четверг 28 мая в Институте языкознания РАН (с возможностью подключения онлайн) состоится состоится заседание семинара «Некоторые применения математических методов в языкознании» им. В.А. Успенского
с докладом Ани Шатских (МГУ) "Автоматическая морфологическая классификация для осетинского языка".
(перенос не состоявшегося ранее доклада)
Время: 28.05.2026, 18:00-19:30.
Место: Математический институт им. В.А. Стеклова РАН, ул. Губкина, д. 8, ауд. 104. Для прохода потребуется студенческий/пропуск любой образовательной или научной организации либо паспорт.
Ссылка для регистрации: https://forms.gle/JHdnkn9ApytBRV8ZA
(все зарегистрировавшиеся получат ссылку для онлайн-подключения; указавшие очное участие будут внесены в список на проход)
Анонс:
Доклад посвящён созданию датасета и нейросетевой модели для автоматической морфологической классификации в осетинском языке. Осетинский язык – иранский язык индоевропейской семьи, распространённый на Северном Кавказе. Этот язык является родным для по меньшей мере 550 тыс. человек и обладает долгой письменной традицией: так, литературный корпус осетинского языка содержит около 12 млн словоупотреблений. Тем не менее, до недавнего времени для осетинского языка не существовало инструментов контекстной морфологической классификации. Эта задача состоит в определении для словоформы её части речи и грамматических признаков (таких как число или падеж) с учётом контекста и является незаменимым уровнем разметки языковых корпусов.
В докладе будет описано создание обучающего корпуса с морфологической аннотацией в системе Universal Dependencies версии 2 (Nivre и др., 2020). Будут рассмотрены вызовы, которые типологические особенности осетинского ставят перед универсальными конвенциями аннотации, и расширения системы UD, принятые в ответ на них. Наконец, будет представлена первая в истории языковая модель архитектуры BERT (Devlin и др., 2019) для осетинского языка и морфологический классификатор на её основе, а также результаты экспериментов, проведённых в ходе создания и улучшения этих моделей.
Литература:
1. Devlin, Jacob и др. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. URL: https://arxiv.org/abs/1810.04805v2
2. Nivre, Joakim и др. (2020). Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection. URL: https://arxiv.org/abs/2004.10643
👨💻1