Кафедра математической логики и теории алгоритмов мехмата МГУ
описание
Учёный секретарь кафедры @ansidiana
329
подписчиков
Охват к подписчикам
73,6%
ERR
Реакции к просмотрам
0,28%
34 на 50 постов
Пересылки к просмотрам
0,78%
94
Постов в день
0,1
всего 392
Где отзываются чаще
доля реакций к просмотрам- 31 мая#матлог #наука Сайт нашей кафедры взламывали 😨 удивительно, но безобидные учёные-математики кому-то показались идеальной целью для сетевой атаки 😞 Теперь сайт обновился и стал ещё лучше! Я потихоньку восстанавливаю материалы. Сейчас я восстановила самое ценное, что там есть - список открытых проблем 😎 Это самые настоящие задачи, которые может решать студент или аспирант!!! https://logic.math.msu.ru/problems/4,23%
- 14 авг.#матлог #наука #конференция Международная конференция «Novikov-125», посвящённая 125-летию со дня рождения П.С. Новикова, пройдёт с 24 по 28 августа 2026 г. в Математическом институте им. В.А. Стеклова Российской академии наук (Москва, ул. Губкина, д. 8). «Новиков-125» — это конференция, посвящённая 125-летию со дня рождения Петра Сергеевича Новикова, который известен своим выдающимся вкладом в алгебру, дескриптивную теорию множеств и теорию доказательств, а также является одним из основателей Московской школы математической логики. Конференция будет покрывать широкий спектр тем в области теории множеств, теории доказательств, алгебры, алгоритмических проблем и теории вычислимости. Программа будет состоять из приглашённых докладов, включая три пленарных исторических доклада, посвящённых работам П.С. Новикова. Страница конференции. Просьба ко всем потенциальным участникам заполнить регистрационную форму (в том числе для участия без доклада). Онлайн-участие возможно.3,16%
- 24 мая#матлог #учёба #спецсеминар 27 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН. Время начала: 16:00 Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533 Л. Д. Беклемишев Пространства Плотта и монотонная логика Гёделя–Лёба Аннотация: В. И. Данилов обнаружил связь между топологической семантикой логики Гёделя–Лёба и структурами, возникшими в 1960-х годах в теории рационального выбора, так называемыми функциями выбора Плотта. В дальнейшем оказалось, что фактически в этой теории речь идет об окрестностных моделях субнормальной модальной логики mGL, которая расширяет логику высказываний правилом монотонности (из A→B выводится □A→□B) и стандартной аксиомой Лёба. В докладе будет рассказано о свойствах этой логики, её моделях, связи с функциями выбора и о других результатах в этом направлении, полученных в последнее время — вместе и по отдельности — В. И. Даниловым, Д. С. Шамкановым, Д. Трофимовым и докладчиком.1,68%
- 3 мая#матлог #спецсеминар #нпммвя В четверг 7 мая в Математическом институте им. В.А. Стеклова РАН (с возможностью подключения онлайн) состоится заседание семинара «Некоторые применения математических методов в языкознании» им. В.А. Успенского с докладом Ани Шатских (МГУ) "Автоматическая морфологическая классификация для осетинского языка". Время: 07.05.2026, 18:00-19:30. Место: Математический институт им. В.А. Стеклова РАН, ул. Губкина, д. 8, ауд. 104. Для прохода потребуется студенческий/пропуск любой образовательной или научной организации либо паспорт. Ссылка для регистрации: https://forms.gle/ZXFQwBmdL4bytWAs8 (все зарегистрировавшиеся получат ссылку для онлайн-подключения; указавшие очное участие будут внесены в список на проход) Анонс: Доклад посвящён созданию датасета и нейросетевой модели для автоматической морфологической классификации в осетинском языке. Осетинский язык – иранский язык индоевропейской семьи, распространённый на Северном Кавказе. Этот язык является родным для по меньшей мере 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.106431,30%
- 2 июн.3 июня в 18:10 состоится заседание научно-исследовательского семинара «С логической точки зрения» («From the Logical Point of View»). А.В. Кудинов НИУ ВШЭ выступит с докладом «Логика SSL и ее сложность» Аннотация Доклад посвящён логике подмножеств пространства (Subset Space Logic, SSL) — бимодальной эпистемической логике с одной модальностью знания (K) и второй модальностью (\Box), соответствующей тому, что агент потратил какие-то ресурсы, чтобы увеличить свои знания. Вторую модальность можно воспринимать, как некоторую динамику, поэтому SSL можно отнести к динамической эпистемической логике. Логика была введена в работе A. Dabrowski, L. S. Moss & R. Parikh «Topological reasoning and the logic of knowledge» (Annals of Pure and Applied Logic, 1996), где, в частности, были предложены её аксиоматизации для класса всех подмножеств и для класса топологических пространств. В работе была доказана финитная аппроксимируемость, дающая оценку сверху на сложность логики SSL, а именно, что SSL лежит в 2EXPTIME. Также очевидно, что SSL - PSPACE-трудна, т.к. в нее погружается логика S4. Более точные оценки долгое время были неизвестны. В работе 2021 года (препринт был в 2019) Гертлингом и Кроммесом (Hertling, Krommes) было доказано, что SSL является EXPSPACE-полной. В докладе мы сделаем короткое введение и постараемся дать представление о том, как доказываются результаты о сложности. Все нужные определения и понятия будут даны, предварительные знания о сложности не требуются, но приветствуются. https://llfp.hse.ru/announcements/1164883547.html1,00%
- 6 мая#матлог #учёба #просеминар 💥В пятницу 8 мая состоится очередное занятие просеминара по математической логике и информатике. ✨Тема: Вполне упорядоченные множества (Яна Захарова, студентка кафедры) ✨Аннотация. Вполне упорядоченные множества (вумы) представляют собой структуры, для которых работает аналог принципа наименьшего числа, верный для множества натуральных чисел. В частности, это свойство вумов позволяет доказывать, что разнообразные процессы не могут длиться бесконечно долго. На просеминаре мы разберём примеры таких задач и обсудим свойства вумов. ✨ Можно заранее порешать задачи (прикреплены к посту). ✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ. ✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi ✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/. ⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼ 📝 ВУМы.pdf0,86%
- 3 мая#матлог #учёба #спецсеминар 6 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН. Время начала: 16:00 Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533 Ю. Д. Теляковская Алгебраические методы изучения звёздной высоты регулярных языков Аннотация: Звёздная высота регулярного языка — минимальное число вложенных итераций Клини ("звёздочек" Клини), необходимое для описания этого языка регулярным выражением. В докладе я сконцентрируюсь на "extended star height" — варианте, допускающем использование в регулярном выражении операций дополнения, объединения, итерации Клини и конкатенации. Основным имеющимся инструментом для изучения свойств регулярных языков при таком определении являются синтаксические моноиды. В докладе будут рассмотрены основные взаимосвязи между звёздной высотой регулярных языков и структурой их синтаксических моноидов. Кроме того, будут упомянуты перспективы использования алгебраических свойств регулярных языков в зависимости от того, существуют ли языки звёздной высоты больше 1.0,63%
- 26 апр.#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), ауд. 313 + Kontur Talk 27.04.2026 В. М. Макаров (СПбГУ, https://www.mathnet.ru/person237482): Ограниченные языки, задаваемые GF(2)-грамматиками (очный доклад) В этом докладе я расскажу о выразительной мощности GF(2)-грамматик: специального семейства формальных грамматик, введённого около 8 лет назад Бакиновой и др. Простыми словами, я про одни семейства языков докажу, что они задаются GF(2)-грамматиками, а про некоторые другие докажу, что они ими не задаются. Семейство GF(2)-грамматик примечательно тем, что у него есть много полезных алгебраических свойств, которыми не обладает семейство обыкновенных бесконтекстных грамматик. Более того, GF(2)-грамматики обобщают однозначные грамматики, что позволяет использовать их хорошие алгебраические свойства для доказательства существенной неоднозначности языков (то есть отсутствия для языка задающей его однозначной грамматики). В основном доклад будет посвящён задаваемости GF(2)-грамматиками ограниченных языков, то есть подмножеств $w_1^* w_2^* \ldots w_k^*$, где $w_1, w_2, \ldots, w_k$ --- любые фиксированные строки. Я докажу сильные необходимые и сильные достаточные условия задаваемости таких языков GF(2)-грамматиками. С помощью полученных результатов я покажу существенную неоднозначность нескольких языков, в том числе языка $\{a^n b^m c^k \mid n \neq m \text{ или } m \neq k \}$, чья существенная неоднозначность долго была открытым вопросом. Все необходимые определения, включая определение GF(2)-грамматик, будут даны в процессе доклада.0,62%
- 12 мая#матлог #учёба #спецсеминар На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ "Модальная и алгебраическая логика" и "Логические методы в информатике" в четверг 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. Видеозаписи предыдущих0,54%
- 8 мая#матлог #учёба #спецсеминар 13 мая 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН. Время начала: 16:00 Место: МИАН (ул. Губкина, 8), ауд. 303 + Контур.Толк Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533 Павел Турянский, Александр Грызлов Гетерогенные колчаны и (ко)пределы, полиморфные по предикативному уровню Аннотация: На докладе покажем практические применения теории категорий для программирования с зависимыми типами. В языках без кумулятивности вселенных типов часто приходится явно поднимать типы до необходимого предикативного уровня, это усложняет формализацию, а иногда и не позволяет без изменений переиспользовать уже описанные конструкции. Используя подход G. Allais [1], можно определить категорные структуры, в которых уровни объектов и морфизмов не задаются константно, а вычисляются, что и позволяет избежать лишних поднятий. Рассмотрим, чем такой подход отличается от уже существующих (agda/cubical, Lean mathlib). Понятия отображаемой структуры [2] и расслоения имеют свои аналоги не только для категорий, но и для рефлексивных графов [3]. Графы обобщаются до гетерогенных колчанов, где начала и концы стрелок лежат потенциально в разных типах, при этом многие конструкции на графах имеют осмысленную версию и на колчанах. В докладе покажем, как можно в гетерогенном стиле сформулировать (ко)пределы. Литература [1] G. Allais. (2019). Generic level polymorphic n-ary functions. URL: https://arxiv.org/abs/2110.06107 [2] B. Ahrens, P. Lumsdaine. (2019). Displayed Categories. URL: https://arxiv.org/abs/1705.04296 [3] J. Sterling. (2024). Reflexive graph lenses in univalent foundations. URL: https://arxiv.org/abs/2404.07854 Докладчик — Павел Турянский.0,50%
- 21 мая#матлог #учёба #просеминар 💥В пятницу 22 мая состоится очередное занятие просеминара по математической логике и информатике. Это последнее занятие в 2025-2026 учебном году. ✨Тема: Клеточные автоматы (Дмитрий Баженов, студент кафедры) ✨Аннотация. Клеточные автоматы представляют собой дискретную систему, меняющуюся с течением времени по локальным правилам: состояние клетки в следующий момент зависит от состояния её самой и её ближайших соседей. Несмотря на простоту модели, клеточные автоматы могут демонстрировать сложное поведение и являются универсальной вычислительной моделью. ✨ Можно заранее порешать задачи (прикреплены к посту). ✅Просеминар проходит по пятницам в 16:45-18:20 в аудитории 1226б Главного здания МГУ. ✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi ✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/. ✅Ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар. 📝 klet2025.pdf0,49%
- 25 мая#матлог #спецсеминар #нпммвя В четверг 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.106430,43%