Кафедра математической логики и теории алгоритмов мехмата МГУ

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

💥В четверг 24 апреля на просеминаре по математической логике и информатике будет продолжение темы "P и NP" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

➰ ВК

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

В пятницу 25 апреля в 14:30 в Математическом институте им. В.А. Стеклова РАН состоится заседание семинара "Некоторые применения математических методов в языкознании".

Где: Математический институт им. В.А. Стеклова РАН, ул. Губкина, д. 8, ауд. 110 (см. информацию о пропусках и онлайн-подключении ниже)
Кто: Валентин Борисович Шехтман (ВШМ МФТИ)
Тема: Временные логики
Аннотация:
Временны́е логики изучают высказывания, зависящие от времени. Такие высказывания возникают в естественном языке и в различных науках: философии, физике, информатике и т.д. С формальной точки зрения, временные логики - это, как правило, модальные логики со специальным синтаксисом и семантикой. На сегодняшний день имеется большое разнообразие таких логик. В докладе будет дан краткий обзор проблематики и результатов в этой обширной области, с упоминанием некоторых приложений.
Для понимания доклада полезно иметь представление о семантике возможных миров.

Если 25 апреля вы собираетесь прийти на заседание семинара в Математический институт и у вас есть пропуск студента/аспиранта/сотрудника научной или образовательной организации (МГУ, ВШЭ, МФТИ, ...), достаточно предъявить этот пропуск и сообщить, что вы идете на семинар "Некоторые применения математических методов в языкознании". Если у вас нет такого пропуска, но вы хотите прийти очно, напишите Степану Львовичу Кузнецову на почту sk@mi-ras.ru.

Онлайн-подключение осуществляется через платформу Контур.Толк; для подключения не требуется на ней регистрироваться.
Для получения ссылки напишите Степану Львовичу Кузнецову на почту sk@mi-ras.ru.

В дальнейшем заседания будут поочередно проводиться в Институте языкознания и Математическом институте, следите за объявлениями.

➰ ВК

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

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
Международная конференция «Формальная философия 2025»

«Формальная философия» – ежегодная международная конференция, которую организует Международная лаборатория логики, лингвистики и формальной философии. В 2025 конференция пройдет в 8-й раз (о прошедших конференциях). Конференция посвящена обсуждению проблематики философской логики, формальной эпистемологии, эпистемической логики, формальной онтологии, аналитической метафизики, философии логики, математической логики, филоcофии математики, а также другим аспектам формальной философии. После конференции пройдет ассоциированное мероприятие – Летняя школа "Логика, лингвистика и формальная философия" (30 июня – 4 июля 2025).

Даты конференции: с 23 по 26 июня 2025

Место проведения: г. Москва, ул. Старая Басманная, д. 21/4, А-307 + Zoom

Формат: гибридный (возможно как очное, так и дистанционное участие)

Рабочие языки: русский и английский

Заявки на участие принимаются до 25 мая.
(https://llfp.hse.ru/formphil2025)

➰ ВК

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

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Kontur Talk (www.mathnet.ru/eng/conf876)

21.04.2025 Anna Dmitrieva (U. of East Anglia, https://research-portal.uea.ac.uk/en/persons/anna-dmitrieva): Complex field with quasiminimal structure (online)

Zilber's Quasiminimality Conjecture states that the complex field equipped with the exponential function is quasiminimal, i.e. every definable subset is countable or co-countable. Despite remaining open, this conjecture led to multiple new concepts and results. One of the directions inspired by the conjecture is the investigation of analogous conjectures where the exponential map is replaced with another function or a function-like object. In most cases the obtained conjecture seems to stay as difficult as the exponential one; as pointed out by Koiran and Wilkie, it even remains open whether adding all entire functions to the complex field would make it quasiminimal or non-quasiminimal. In this talk we provide two quasiminimal examples of this sort: first one involves a correspondence between two elliptic curves, while the second one considers the theory of a generic function, as introduced by Zilber in 2002.

➰ ВК

#матлог #наука #семинар

Приглашаем принять участие в очередном, 9-м по счету Колмогоровском семинаре по компьютерной лингвистике, который состоится 25 апреля 2025 года.

Место проведения - Покровский бульвар, 11.

Семинар пройдет в смешанном формате.

Информация о семинаре и регистрация доступна по ссылке https://cs.hse.ru/clls/2025/

➰ ВК

#матлог #новости

В выпуске (№ 1, январь-февраль) журнала "Вестник Московского университета. Серия 1. Математика. Механика" вышла обзорная статья, посвящённая нашей кафедре!

Серия обзорных статей в "Вестнике" приурочена к 270-летию Московского университета.

Со статьёй о кафедре математической логики и теории алгоритмов можно ознакомиться по ссылке.

http://vestnik.math.msu.su/issues/2025/1/04.pdf

➰ ВК

Внимание!
Изменение аудитории семинара "Категориальные грамматики" https://m.vk.com/wall-70743963_2021

Аудитория: 424 (2 гуманитарный корпус)

➰ ВК

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

В пятницу 18 апреля в 14:30 на заседании семинара "Некоторые применения математических методов в языкознании" в Институте языкознания РАН состоится продолжение доклада С.Г. Татевосова и П.О. Россяйкина. Ссылка для подключения в Zoom та же. Если вы не регистрировались на первую часть доклада, но хотите прийти или подключиться онлайн, заполните форму: https://forms.gle/jFsZcNFbbx15GskT7. (Записавшиеся «очно» будут внесены в списки на проход в здание ИЯз РАН.) Уже зарегистрировавшимся это делать не нужно.

Запись первой части доклада будет разослана всем зарегистрировавшимся, а также опубликована на странице семинара в ближайшие дни http://tipl.philol.msu.ru/index.php/science/seminars/npmmvia. По всем вопросам пишите на почту npmmvia@mail.ru.

Когда: 14:30 18 апреля 2025 года
Где: Институт языкознания РАН, конференц-зал + онлайн
Кто: Сергей Георгиевич Татевосов (МГУ), Петр Олегович Россяйкин (МГУ)
Название: "Новое в семантике: о двух явлениях и всем остальном. Часть 2"
Аннотация:
В этом докладе мы рассмотрим несколько сюжетов, которые вписываются в две аналитические тенденции современной формальной семантики: (i) модальный анализ языковых выражений и явлений, традиционно не относимых к модальным; (ii) семантический анализ явлений, традиционно относимых к прагматике. А именно, преимущественно на материале русского языка, мы обсудим некоторые аргументы в пользу синтаксического представления речевых актов и модальный анализ перфектива (и, по возможности, некоторых других грамматических сущностей).

➰ ВК

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

Ближайший семинар «Категориальные грамматики» состоится 17 апреля (17.04.2025).

Начало: 18:30. Аудитория: 1605, кафедра математической логики и теории алгоритмов (возможно, аудитория изменится).

Докладчик: Т.Г. Пшеницын
Тема: Грамматики слияния, сохраняющие связность

Рассматриваются ориентированные гиперграфы, гиперребра которых помечены символами некоторого алфавита. У каждого символа есть комплементарный ему. На гиперграфах определена операция слияния: два гиперребра с комплементарными метками "склеиваются" и удаляются. В грамматике слияния разрешено брать неограниченное число изоморфных копий гиперграфов из фиксированного конечного набора и применять к ним слияния; грамматика порождает компоненты связности получающихся таким образом гиперграфов. Мотивация изучения такого формализма связана с моделированием взаимодействия молекул ДНК; можно смотреть на грамматики слияния и как на своеобразное логическое исчисление с "правилом сечения" (выводимые объекты такого исчисления — связные гиперграфы).

При исследовании алгоритмических и теоретико-языковых свойств грамматик слияния возникли трудности, связанные с тем, что слияние может приводить к нарушению связности: при слиянии между двумя связными гиперграфами или внутри одного связного гиперграфа может получаться несвязный гиперграф. Чтобы исключить нарушения связности, в литературе было введено понятие грамматик слияния, сохраняющих связность. Оказалось, что для них многие задачи решаются проще, чем для грамматик слияния в целом (проще — и в смысле алгоритмической сложности, и в смысле простоты доказательств). Так, Aaron Lye в 2021 году доказал, что задача непустоты для грамматик слияния, сохраняющих связность, разрешима и является NP-полной; также он получил аналогичный результат в отношении задачи принадлежности для существенных грамматик слияния, сохраняющих связность. Докладчиком также был доказан аналог теоремы Париха для грамматик слияния, сохраняющих связность (верно ли это для всех грамматик слияния, неизвестно).

В докладе будет описано свойство сохранения связности и будет дан обзор упомянутых выше результатов. Основной акцент будет сделан на сложности самого свойства сохранения связности: будет доказано, что задача проверки, сохраняет ли грамматика слияния связность, разрешима, принадлежит классу coNEXPTIME и при этом PSPACE-трудна. Доказательства иллюстрируют типичные для данной области методы.

➰ ВК

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

💥В четверг 17 апреля на просеминаре по математической логике и информатике будет тема "P и NP" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅Можно заранее порешать задачи (прикреплены к посту).
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

📝 P_NP_2025

➰ ВК

#матлог #наука #спецсеминар #не_мехмат #МГУ

Научно-исследовательский семинар кафедры логики философского факультета МГУ "Современная логика"

Дата, время и аудитория: 17.04.2025 (чт) в 13.30 в г354it.
Место: Шуваловский корпус МГУ
Докладчик: С. О. Сперанский (МИАН)
Название: О кванторной версии модальной логики Белнапа–Данна
Аннотация: Речь пойдёт о кванторной версии пропозициональной модальной логики BK из статьи С.П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) четырёхзначная система Белнапа–Данна; эта версия будет обозначаться через QBK. В ходе доклада мы обсудим адаптацию метода канонических моделей для QBK и её расширений. В частности, с помощью этой адаптации получается теорема о сильной полноте для QBK относительно подходящей семантики возможных миров.

Доклад основан на совместной статье:
A.V. Grefenshtein, S.O. Speranski. On the quantified version of the Belnap–Dunn modal logic. Sbornik: Mathematics 215(3), 323–354, 2024. https://doi.org/10.4213/sm9981e

По вопросам прохода в корпус пишите на почту ivan.slusarev@mail.ru или в тг @ivanslsrv (лучше до этой среды включительно).

➰ ВК

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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдёт в среду 16 апреля.
Время проведения семинара 14:00.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идете на семинар ВШМ и предъявить паспорт.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Дворкин Лев

Название: Финитная аппроксимируемость расширений wK4, наследуемых подшкалами (часть 1)

Подшкалой шкалы Крипке (X; R) называется подмножество S носителя X с индуцированным отношением достижимости. Логика L наследуется подшкалами Крипке, если класс её шкал Крипке замкнут относительно взятия подшкал. Файн доказал, что все полные по Крипке расширения K4, наследуемые подшкалами, финитно аппроксимируемы. Данный результат был усилен Захарьящевым на случай логик, наследуемых конфинальными подшкалами (подшкалами, носитель которых конфинален в исходной шкале). Доказательства Файна и Захарьящева основываются на семантике Крипке. Бежанишвилли, Гильярди и Джибладзе дали чисто алгебраическое доказательство результатов Файна и Захарьящева, одновременно обобщив их на расширения wK4 = K + p → p \/ p. Разбору доказательства последнего результата и посвящён доклад. В первой части мы обсудим некоторые факты, касающиеся алгебраической семантики модальных логик. В отличие от семантики Крипке, данной семантике уделяют мало времени в курсах по модальной логике, поэтому мы остановимся на ней достаточно подробно. Вторая часть посвящена непосредственно доказательству результата. От слушателей предполагается знание базовых фактов о модальных логиках и семантике Крипке.

➰ ВК

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

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

21 April 2025, 17.30 CET = 18.30 Moscow time

Speaker: Ivan Baburin
Title: Universality in Asynchronous Cellular Automata

Abstract:
A cellular automaton is a dynamical system consisting of an infinite array of cells, such that each cell uses a local neighborhood to perform a transition. An asynchronous cellular automaton (ACA) is a modification of cellular automata where every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellular automata and show that—despite their fundamental differences—most asynchronous automata can invariantly “simulate” their synchronous counterparts [1]. To achieve that, we present two characterizations of invariance in asynchronous automata: – An algebraic approach using the notion of commutativity, as introduced by G´acs [2]. – A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some of the smallest universal ACAs [3]. Finally, we discuss the limits of asynchronous computation by demonstrating that for certain automata neither universality nor reliable simulation can be achieved. Further Reading More details can be found in the corresponding paper [3].

References
1. T. Worsch, “Towards intrinsically universal asynchronous ca,” Natural Computing, vol. 12, no. 4, pp. 539–550, 2013.
2. P. Gacs, “Deterministic computations whose history is independent of the order of asynchronous updating,” 2001.
3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.

➰ ВК

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

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (www.mathnet.ru/eng/conf876)

14.04.2025 L. D. Beklemishev: Fragments of arithmetic and cyclic proofs (onsite, https://homepage.mi-ras.ru/~bekl/)

(jww with Daniyar Shamkanov and Ivan Smirnov)

We present an alternative cyclic proof system for Peano arithmetic that could be simpler than the existing ones and well-adapted both for proof analysis and for automatizing inductive proof search. In addition, we show how various traditional subsystems of Peano arithmetic defined by restricted forms of induction can be represented as fragments of the proposed system.

➰ ВК

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

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

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

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Никита Лукашов

Название: Алгебраическая унификация в модальных логиках

Аннотация:

Проблема символической унификации для логики L — это достаточно естественный вопрос, имеет ли данная формула \phi унификатор в логике L. Другими словами, существует ли такая подстановка \sigma для формулы \phi, что постановочный пример \sigma(\phi) является теоремой логики L. Несмотря на простоту формулировки, проблема унификации является довольно сложной, и ещё многое предстоит сделать в этой области.

В своём докладе я предоставлю алгебраический взгляд на проблему унификации в нормальных модальных логиках. Точнее, мы посмотрим на проблему унификации в этих логиках с точки зрения алгебраической семантики. По ходу доклада мы определим модальные алгебры для произвольных нормальных модальных логик и докажем их универсальные свойства. Затем мы подробно поговорим про проективные алгебры и их эквивалентные определения (в частности, покажем их связь с проективными формулами). После чего мы определим алгебраический тип унификации через эти проективные алгебры и докажем фундаментальную теорему, утверждающую, что два типа унификации — алгебраический и символический — для произвольных нормальных модальных логик совпадают.

В заключение мы поговорим про точные формулы в нормальных модальных логиках, об условии, которое они задают для модальных алгебр, и получим новое алгебраическое доказательство известного факта, что проективные формулы всегда являются точными. Наконец, с помощью результатов С. Гильярди мы покажем, что в некоторых модальных логиках, таких как K4, S4, GL и др., верно обратное, т.е. точные и проективные формулы в этих логиках совпадают.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
11 апреля (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Black Boxes: The Semantics and Logic of Obliterative Modalities.

Докладчик: Элиа Дзардини.

Аннотация: If we wish to analyse knowability (and similar notions) in terms of some kind of possibility of knowledge, troubles quickly arise if the possibility in question is supposed to obey some very basic modal principles (like law 4 or the law of distribution). In this paper, I first provide an informal explanation of the notion of possibility in question. I then proceed to show how this informal explanation can be turned into a natural formal possible-world semantics with a multiplicity of accessibility relations, which gives rise to a nonregular modal logic that avoids the above-mentioned troubles. After introducing a sound and complete axiomatization of the logic, I close by mentioning some philosophically interesting directions in which the basic system can be extended or modified.

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

Анонс: https://llfp.hse.ru/announcements/1033740295.html

➰ ВК

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

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

Время: 15 апреля 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

Сергей Славнов (НИУ ВШЭ, https://www.hse.ru/org/persons/61709453/)

Индексированное исчисление Ламбека с передвижением

Исчисление Ламбека обычно интерпретируют как логику строк и конкатенации строк; именно в таком качестве оно используется в лингвистических приложениях. Однако давно замечено, что с точки зрения лингвистических приложений такой простой структуры обычно оказывается недостаточно, и требуется рассматривать более сложные объекты и операции.

Мы определяем специфическую алгебру термов, которые обозначают упорядоченные последовательности строк и могут комбинироваться между собой более сложными способами, чем простая конкатенация. Далее мы вводим систему типов для таких термов. Эта система представляет собой неассоциативное, но частично коммутативное расширение исчисления Ламбека, которое нам кажется с одной стороны достаточно простым и интересным, а с другой стороны достаточно выразительным.

➰ ВК

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

🔥Возобновляет работу семинар "Некоторые применения математических методов в языкознании"! Это старейший семинар по математической лингвистике в России, одним из первых организаторов которого был Владимир Андреевич Успенский, в котором принимали участие Алексей Всеволодович Гладкий, Игорь Александрович Мельчук, Елена Викторовна Падучева и другие известные ученые. С 2025 года семинар проводится совместно Московским государственным университетом им. М.В. Ломоносова и Российской академией наук — Математическим институтом и Институтом языкознания.

Заседания будут проходить поочередно в ИЯз РАН и МИАН.

Когда: 11 апреля 2025 года, 14:30
Где: Институт языкознания РАН (Большой Кисловский пер., д. 1, стр. 1), конференц-зал + онлайн (ссылка отправляется зарегистрированным участникам)
Кто: Сергей Георгиевич Татевосов, Петр Олегович Россяйкин
Название: "Новое в семантике: о двух явлениях и всем остальном"
Аннотация:
В этом докладе мы рассмотрим несколько сюжетов, которые вписываются в две аналитические тенденции современной формальной семантики: (i) модальный анализ языковых выражений и явлений, традиционно не относимых к модальным; (ii) семантический анализ явлений, традиционно относимых к прагматике. А именно, преимущественно на материале русского языка, мы обсудим некоторые аргументы в пользу синтаксического представления речевых актов и модальный анализ перфектива (и, по возможности, некоторых других грамматических сущностей).

Для оформления пропуска в Институт языкознания или для получения ссылки для подключения онлайн необходимо заполнить форму до 23:59 10 апреля: https://forms.gle/jFsZcNFbbx15GskT7

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

➰ ВК