#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

8 December, 18:30 MSK

Sasha Kozachinskiy

Language identification and generation in the limit.

Assume we have a family of formal languages F. An adversary selects a language L from F and starts enumerating elements of L in some order. Our task is to guess L after seeing finitely many elements of the enumeration. If there is an algorithm that does it regardless of the adversary's actions, we call F identifiable in the limit. Angluin (1980) have obtained necessary and sufficient conditions for countable families to be identifiable in the limit and gave an example of the family of "pattern languages", satisfying these conditions.

Kleinberg and Mullainathan have recently considered a variation of this setting, where the task is not to guess L but to indicate an infinite subset of L after finitely many steps. Families, for which this is possible, are called generatable in the limit. They have shown that any countable family is generatable in the limit. Moreover, it can be done computably whenever membership query for the family is decidable. In the talk I will cover these results.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар отдела математической логики, Logic Online Seminar (https://www.mathnet.ru/rus/conf876)

Время: 8 декабря 2025 (понедельник), начало — в 18:00 по Москве
Место: МИАН, ауд. 530 + Контур.Толк

❗ Обращаю внимание на нестандартное время проведения семинара (18:00 вместо 16:00) и нестандартную аудиторию (530 вместо 313) ❗

С.П. Одинцов (ИМ СО РАН, https://www.mathnet.ru/rus/person/27585/): Семантика множеств ответов и её логические аспекты

Семантика устойчивых моделей/множеств ответов Гельфонда и Лифшица (1988) стала первым примером семантики логических программ с оператором «отрицание-как-неудача» (в пропозициональном языке), которая не зависела от типа рекурсивной зависимости между определяемыми параметрами. Эта семантика дала начало отдельной парадигме в рамках логического программирования, а именно программированию множеств ответов (англ. answer set programming, сокр. ASP). Определение множеств ответов опиралось на синтаксическое преобразование программы и последующее нахождение наименьшей неподвижной точки, а отношение следования, определяемое данной семантикой, было немонотонным.

В докладе будет дан обзор результатов, показывающих, что программы с отрицанием можно трактовать как логические объекты. Оказывается, множества ответов можно рассматривать как минимальные (в определенном смысле) модели логики «здесь-и-там», обозначаемой через HT (Пирс 1996); в этом смысле HT является монотонной базой для ASP-следования. Более того, для НТ можно доказать теорему сильной эквивалентности: НТ-эквивалентные фрагменты программ можно заменять друг на друга с сохранением множеств ответов. Аналогичные результаты можно получить для логических программ с двумя типами отрицаний: отрицание-как-неудача и сильное отрицание, — а также для паранепротиворечивой версии PAS семантики множеств ответов (Одинцов, Пирс 2005). При этом дедуктивной базой для PAS является конечно-значное расширение конструктивной логики Нельсона.

Наконец будет показано, что немонотонные следования ASP и PAS допускают точные вложения в монотонные модальные теории.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

11 декабря 2025 г. доклад В.Л. Селиванова и И.В. Смирнова (СПбГУ) «О высоте гомоморфных порядков конечных размеченных деревьев».

Время: 16:00
Место: МИАН, ауд. 104 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

Аннотация:
Работа относится к теории стройных порядков, т.е. фундированных частичных порядков, не имеющих бесконечных антицепей. Эта теория является популярным разделом бесконечной комбинаторики с интересными применениями к ряду областей математики и теоретической информатики. Как принято в теории стройных порядков, наши обозначения для простоты не различают предпорядок и его фактор-порядок по индуцированному отношению эквивалентности. Мы сосредоточимся на вычислении высоты h(Q) некоторых стройных порядков Q, т.е. супремума ординалов, изоморфно вложимых в Q. Точнее, изучим высоту так называемого гомоморфного порядка, определяемого следующим образом. Сопоставим любому предпорядку Q гомоморфный предпорядок T(Q) конечных Q-размеченных деревьев (T,t), где T - конечное дерево, t - его разметка, и (T,t) \leq_h (U,u), если существует монотонная функция f из T в U такая, что t(x) \leq_Q u (f(x)) для любого x из T.

Из теоремы Краскала о дереве следует, что если порядок Q стройный, то порядок T(Q) тоже стройный. Основной результат состоит в установлении оптимальной верхней оценки ординала h(T(Q)) в зависимости от h(Q). Оценка получена в виде подходящих ординалов Веблена. В качестве следствий вычислим высоту некоторых конкретных гомоморфных порядков, изучавшихся в литературе.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
10 декабря в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Алгоритмическая сложность кооперативной игры "Ханаби".

Докладчик: Анастасия Оноприенко (к.ф.-м.н., департамент больших данных и информационного поиска).

Аннотация: Игры представляют собой вид человеческой деятельности, где условия задачи совершенно ясны и легко формализуются. В некоторых видах игр, таких как шахматы и го, успешная игра рассматривается как высшее достижение человеческого, «естественного» интеллекта. С середины XX столетия игры рассматриваются в качестве полигона для тестирования возможностей компьютера. Игры часто представляют собой примеры многоагентного взаимодействия участников с противоположными интересами. Однако «Ханаби» является примером игры сотрудничества, вкоторой участники совместно достигают общей цели. На данный момент успехи ИИ в игре «Ханаби» довольно скромные: компьютеру ступает даже командам из игроков-новичков. Очевидное препятствие для «лобового» решения задачи автоматизации игры – «экспоненциальный взрыв». С одной стороны, такой «взрыв» очевиден на практике при попытке запрограммировать игру, а с другой стороны, математически это выражается в виде утверждения об NP-трудности соответствующих вычислительных задач. NP-полнота игры «Ханаби» была установлена даже для простейшего варианта игры в случае одного игрока, который видит всю колоду и пытается «разложить пасьянс»: выложить на столе карточки всех цветов. При этом карточки каждого цвета должны выкладываться по возрастанию (на каждой карточке написано число), и в любой момент времени у игрока в руке может быть лишь небольшое (заранее фиксированное) количество карт. Нами установлена точная граница параметров игры «Ханаби», при которой она всё ещё остаётся NP-полной, а при уменьшении любого из этих чисел игра «Ханаби» перестаёт быть NP-трудной (разумеется, если P не равно NP). Найденные нами значения параметров оказываются очень маленькими, что демонстрирует практическую невозможность точного анализа «Ханаби» даже при небольших параметрах игры.
_____________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1108058816.html

➰ ВК

#матлог #учёба #просеминар

💥В среду 10 декабря состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Полугруппы с делениями" (Пшеницын Тихон, выпускник кафедры, аспирант МИАН).
✨Аннотация. Бинарные отношения с операцией композиции, формальные языки с операцией конкатенации, компакты R^n с суммой Минковского — примеры полугрупп с делениями. На каждой из этих структур можно определить операции левого деления a\b и правого деления b/a, связанные с полугрупповой операцией соответствием Галуа. На занятии мы исследуем различные виды полугрупп с делениями и сравним их с точки зрения того, какие законы в них выполняются. Мы также рассмотрим смежный вид структур — прегруппы — и разберем пример, как ученые с помощью прегрупп описывают синтаксис предложений естественных языков.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 Handout_Proseminar_Residuated_Semigroups.pdf

➰ ВК

#матлог #спецсеминар #нпммвя

В четверг 11 декабря в Институте языкознания РАН (с возможностью подключения онлайн) состоится заседание семинара «Некоторые применения математических методов в языкознании» с продолжением доклада Максима Евгеньевича Вишникина "Категориальные грамматики с ограничением на количество присваиваемых категорий".

Время: 11.12.2025, 14:00-15:30.
Место: Институт языкознания РАН, Большой Кисловский пер., 1, стр. 1, конференц-зал. Для прохода необходимо зарегистрироваться по ссылке ниже и взять с собой паспорт.

Ссылка для регистрации: https://forms.gle/RwXRf33JE3CP1bHBA
(все зарегистрировавшиеся получат ссылку для онлайн-подключения; если вы регистрировались на первую часть, ссылка придёт автоматически)

Тема: Категориальные грамматики с ограничением на количество присваиваемых категорий (продолжение)

Анонс:
В первой части было рассказано о математической формализации того, как агент усваивает грамматику из корпуса примеров (обучаемость по Голду). Во второй части будет обсуждаться разновидность грамматик, обучаемых по Голду — базовые категориальные грамматики с однозначным присвоением категорий.

Сайт семинара: http://tipl.philol.msu.ru/index.php/science/seminars/npmmvia

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар отдела математической логики, Logic Online Seminar (www.mathnet.ru/rus/conf876)
Proof Society Seminar (https://www.proofsociety.org/proof-society-seminar/)

Время: 15 декабря 2025 (понедельник), начало — в 16:00 по Москве
Место: онлайн

Anton Freund (Wuerzburg University): Approaching Girard's functor Lambda

Abstract: Girard has claimed that Pi^1_1-comprehension corresponds to his functor Lambda on dilators. He described a plausible proof around 1980, but it seems that details remain difficult. This talk presents joint work with Aguilera and Weiermann, in which we give a detailed proof that Pi^1_1-comprehension corresponds to a variant of Lambda, namely the functor J of Päppinghaus. No prior knowledge of dilators is assumed.

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 10 декабря в 14:00.

Место проведения:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.

Название: Введение в семантику первопорядковых модальных логик - часть 4

Докладчик: В.Б. Шехтман

Аннотация:
Доклад основан на вводных лекциях о семантике первопорядковых модальных логик, прочитанных совместно с Д. Шкатовым летом 2025 года в рамках ESSLLI 2025. Будут изложены детали доказательства теоремы о полноте Танаки-Оно, связь полноты в шкалах и пучках Крипке (примеры неполных логик и теорема Судзуки).

➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

12 декабря 2025 г.

Г. Г. Черевиченко
"Определение подстановки и альфа-конверсии методом Jean-Louis Krivine".
Аннотация: доказать что-либо строго про подстановку и альфа-конверсию мучительно трудно, поэтому проблему почти всегда замалчивают. Но есть интересные нестандартные подходы, самым неожиданным из которых, видимо, является подход Кривина.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 108 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

Дата и время: 12.12.2025 в 16:20

Название: Суперструктуры и нестандартный анализ

Докладчик: Лапушкин Евгений

Аннотация:
В докладе будет представлен подход к нестандартному анализу через суперструктуры и его теоретико-модельные аспекты.
Для множества X, содержащего базовые элементы того или иного математического контекста, мы построим универсум V(X), который содержит всевозможные объекты, которые могут понадобиться при работе с X. Этот универсум задает естественную модель в языке с символом принадлежности, где формулы с ограниченными кванторами допускают естественную интерпретацию. Мы обсудим принцип переноса, внутренние и внешние множества, а также посмотрим на приложения.

➰ ВК

#матлог #учёба #просеминар

💥В среду 17 декабря состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Полугруппы с делениями - продолжение" (Пшеницын Тихон, выпускник кафедры, аспирант МИАН).
✨Аннотация. Бинарные отношения с операцией композиции, формальные языки с операцией конкатенации, компакты R^n с суммой Минковского — примеры полугрупп с делениями. На каждой из этих структур можно определить операции левого деления a\b и правого деления b/a, связанные с полугрупповой операцией соответствием Галуа. На занятии мы исследуем различные виды полугрупп с делениями и сравним их с точки зрения того, какие законы в них выполняются. Мы также рассмотрим смежный вид структур — прегруппы — и разберем пример, как ученые с помощью прегрупп описывают синтаксис предложений естественных языков.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 Handout_Proseminar_Residuated_Semigroups.pdf

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

15 December, 18:30 MSK

Sasha Kozachinskiy

Language identification and generation in the limit.

I will finish my talk about language generation, this time I will present some about language generation for regular and context-free languages.

Annotation of the first part is below.

Assume we have a family of formal languages F. An adversary selects a language L from F and starts enumerating elements of L in some order. Our task is to guess L after seeing finitely many elements of the enumeration. If there is an algorithm that does it regardless of the adversary's actions, we call F identifiable in the limit. Angluin (1980) have obtained necessary and sufficient conditions for countable families to be identifiable in the limit and gave an example of the family of "pattern languages", satisfying these conditions.

Kleinberg and Mullainathan have recently considered a variation of this setting, where the task is not to guess L but to indicate an infinite subset of L after finitely many steps. Families, for which this is possible, are called generatable in the limit. They have shown that any countable family is generatable in the limit. Moreover, it can be done computably whenever membership query for the family is decidable. In the talk I will cover these results.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН

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

Общеинститутский семинар по математике и её приложениям (https://www.mathnet.ru/conf142)

Семинар состоится в четверг 18 декабря 2025 года в 16 часов в
МИАН, ул. Губкина, 8, в конференц-зале на 9-м этаже,
а также Онлайн, в сервисе Kontur Talk.

Кандидат физ.-матем. наук С. О. Сперанский

"Вычислительные аспекты элементарных теорий классов вероятностных пространств"

Аннотация:

Доклад будет посвящён алгоритмическим вопросам для элементарных теорий различных классов вероятностных пространств (конечных, дискретных, произвольных, безатомных). При этом будут рассмотрены как теории в односортном языке с переменными по событиям, так и теории в двухсортном языке, дополнительно содержащем переменные по вещественным числам. Кроме того, внимание будет уделено «слабым» пространствам, в которых меры подразумеваются конечно-аддитивными, но не обязательно счётно-аддитивными; такого рода пространства используются в семантике многих вероятностных логических систем, возникающих в теоретической информатике. Стоит отметить, что хотя основное внимание будет сосредоточено на языках, близких к традиционно изучаемым элементарным языкам полей и решёток, у практически всех сопутствующих результатов имеются естественные аналоги для так называемых «первопорядковых логик вероятности», которые возникли в работах Дж. Хальперна и чьи варианты продолжают активно изучаться (например, группой З. Огняновича в Белграде).

➰ ВК

#матлог #учёба #спецсеминар

17 декабря в 18:10 состоится 107-е заседание научно-теоретического семинара «Формальная философия».

Тема доклада: Теория научного объяснения Ч. С. Пирса. От трёх типов рассуждения – к типологии научных объяснений".

Докладчик: Вера Шумилина.

Аннотация: Проблема существования (и конструирования) универсальной единой теории научного объяснения считается закрытой (Woodward & Ross, 2021). Со времени ее постановки Гемпелем и Оппенгеймом (1948) прошло лишь несколько десятилетий, когда существующий плюрализм теорий в различных дисциплинах (Mancosu et al., 2023; Machamer et al., 2000) поставил под вопрос возможность единой, подходящей для всех дисциплин, а не ориентированной на законосообразные физические объяснения, теории научного объяснения.

Продолжающийся в рамках эпистемологии научных объяснений спор эпистемических, включая унификационизм (Friedman, 1974; Kitcher, 1981, 1989), модель охватывающих законов (Hempel, 1965) и прагматический подход (van Fraassen, 1980), теорий с онтическими, в первую очередь каузальными моделями (Salmon, 1984; Woodward, 2003), показал нерелевантность нормативной установки в отношении теорий научного объяснения.

Сложившуюся к концу 20 века ситуацию в философии науки усугубил и методологический разрыв с логическими теориями объяснения (Douven, 2025). В докладе будет представлена теория, позволяющая разрешить противоречия логического, методологического и философско-научного подходов к теории научного объяснения на основании реконструированной теории научного объяснения Ч.С. Пирса. Она, в свою очередь, основана на типологии рассуждений как стадий научного исследования.

Реконструкция фокусируется на соблюдении эпистемологических требований. Показано, что теория соблюдает требования как эпистемического (связь объяснения и предсказания, обоснование объяснений), так и онтического (учёт различных отношений зависимости в объяснениях, обеспечение понимания) подхода.
_____________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1110099141.html

➰ ВК

#матлог #наука #ВШЭ #конференция

29 декабря на факультете компьютерных наук НИУ ВШЭ пройдёт мини-конференция «Logic Matters 2025» (программа ниже).

Место проведения — Москва, Покровский б-р, д. 11, ауд. F301. Планируется также возможность онлайн-подключения.

Для участия (в т.ч. получения пропуска в здание ВШЭ) нужно зарегистрироваться на странице https://cs.hse.ru/ai/clst/issa/logmatters/ . Просьба желающим зарегистрироваться как можно быстрее, во всяком случае, не позже четверга 25 декабря (если нужен пропуск).

Программа конференции:

10:00 — 10:30 сбор участников

10:30 — 10:45
Вступительное слово
Кузнецов Сергей Олегович, Директор Центра языковых и семантических технологий ФКН, НИУ ВШЭ

10:45 — 11:15
Строго позитивные логики и стройные порядки
Беклемишев Лев Дмитриевич, Математический институт им. В.А. Стеклова РАН, НИУ ВШЭ

11:15 — 11:45 кофе-брейк

11:45 — 12:15
Пайплайн для верификации сгенерированных LLM решений математических задач
Сазонова Варвара Андреевна, Московский государственный университет имени М.В.Ломоносова

12:15 — 12:30 перерыв

12:30 — 13:00
О вопросах сходимости и генерализации для нейронных схем малой глубины
Разборов Александр Александрович, Математический институт им. В.А. Стеклова РАН, University of Chicago

13:00 — 14:00 обед

14:00 — 14:30
AI в математике: последние новости
Николенко Сергей Игоревич, Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН (онлайн)

14:30 — 14:45 перерыв

14:45 — 15:15
Табличное разрешение классов типов
Соколов Павел Павлович, НИУ ВШЭ

15:15 — 15:45 кофе-брейк

15:45 — 16:15
О замыкающих ординалах для первопорядковых логик вероятности с распределением на носителе
Сперанский Станислав Олегович, Математический институт им. В.А. Стеклова РАН, НИУ ВШЭ

16:15 — 16:30 перерыв

16:30 — 17:00
Сложность эквациональных теорий двух классов решеток Клини с делениями
Кузнецов Степан Львович, Математический институт им. В.А. Стеклова РАН, НИУ ВШЭ

17:00 — …
Общая дискуссия «Могут ли нейронки рассуждать?»
Закрытие конференции

➰ ВК