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

Journées sur les Arithmétiques Faibles
Weak Arithmetics Days 44

https://workshop.math.cas.cz/JAF44/

8-10 September 2025, Prague, Czech Republic
Aim. Weak arithmetics play a fundamental role in several areas of philosophy, mathematics, and computer science, by studying the nature and properties of natural numbers from a logical point of view. The aim of the conference is to provide a forum for researchers to present their results to members of communities who study or apply weak arithmetics in various fields and formalisms. Previous JAFs.

Topics. Proofs in arithmetic with restricted system of axioms; non-standard models of such systems; decidability, undecidability, and complexity of arithmetical theories; definability in arithmetic structures; machines, automata and words, related to arithmetic; finite model theory, word structures.

Location. Institute of Mathematics, Czech Academy of Sciences. The institute is in the centre of Prague, a few minutes walk from Wenceslas Square.

Programme. TBA; confirmed speakers

Albert Atserias, Technical University of Catalonia
Leszek Kołodziejczyk, University of Warsaw
Jan Krajíček, Charles University
Contributed papers. Authors are invited to send an abstract not exceeding three pages as an electronic submission in the form of a pdf file, to be sent both to cegielski@u-pec.fr and to thapen@math.cas.cz. Submissions are to be received before 2 June 2025. Authors will be notified of acceptance before 5 July 2025.

Registration. To register, send your details (full name, affiliation, planned dates of arrival and departure) to thapen@math.cas.cz. There is no conference fee.

Financial support. We have some funds to support students coming to Prague to attend the conference. Please contact Neil Thapen, thapen@math.cas.cz, to apply.

Contact. For any enquires contact Patrick Cégielski, cegielski@u-pec.fr or Neil Thapen, thapen@math.cas.cz.

JAF steering committee. Patrick Cégielski (Paris XII), Julien Cervelle (Paris XII), Andrés Córdon-Franco (Seville), Ali Enayat (Göteborg), Costas Dimitracopoulos (Athens), Alex Esbelin (Clermont-Ferrand), Neil Thapen (CAS)

Local organizing committee. Neil Thapen (CAS), Pavel Hrubeš (CAS), Ondřej Ježil (Charles University)

➰ ВК

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

В среду 16 апреля 2025 г. в 18:30 в аудитории 1402 состоится научная конференция студентов, аспирантов и молодых ученых "Ломоносов - 2025".

Будут представлены доклады:

18:30-18:50 Аллеманд Аллан Олегович
"Топологическая теория разрешимости некоторых уравнений в элементарных функциях методом Арнольда"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476634/181905/uid494087_report.pdf

18:50-19:10 Вишникин Максим Евгеньевич
"Базовые категориальные грамматики с ограничением на количество присваиваемых категорий"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1485934/186601/uid563464_report.pdf

19:10-19:30 Хайруллин Артур Миннахматович
"Вычисления с частичным оракулом"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1486507/186915/uid567073_report.pdf

19:30-19:50 Холодилов Филипп Дмитриевич
"О множествах натуральных чисел, замощающих натуральный ряд"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476552/181859/uid683528_report.pdf

19:50-20:10 Deng Zhibo
"On the equivalence checking problem for deterministic top-down tree automata"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476139/181592/uid952894_report.pdf

➰ ВК

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

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

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

К.А. Ковалёв (МФТИ)

Об интерпретациях полей в о-минимальных расширения вещественно замкнутых полей — 2

На предыдущем докладе мы сделали небольшой обзор результатов, связанных с понятием о-минимальности, и начали доказывать основной результат об интерпретируемости областей целостности в о-минимальных обогащениях вещественно замкнутых полей. Настоящий доклад начнётся с повторения схемы доказательства результатов, которые обсуждались ранее, в том числе мы остановимся подробнее на местах, которые «заметались под ковёр». Далее, мы завершим доказательство основного результата, идея которого кратко обсуждалась в конце предыдущего доклада. Кроме того, мы обсудим схему доказательства результатов, на которые мы ссылались (в частности, о введении структуры определимого многообразия на определимых группах).

Ссылка на предыдущий доклад: https://www.mathnet.ru/rus/present45786

➰ ВК

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

С прискорбием сообщаем, что 4 апреля 2025 года на 82-м году жизни скончалась Лариса Львовна Максимова — выдающийся математик, доктор физико-математических наук, главный научный сотрудник Института математики им. С. Л. Соболева СО РАН, ученица выдающегося алгебраиста и логика Анатолия Ивановича Мальцева.

Лариса Львовна вошла в историю как один из ведущих специалистов по неклассическим логикам. Её работы по модальным и суперинтуиционистским логикам стали классикой математической логики и получили международное признание. В 2018 году была награждена медалью института математики СО РАН «За выдающийся вклад в математику».

До последних дней Лариса Львовна сохраняла ясность мысли — её последняя статья увидела свет в начале 2024 года.

Для многих поколений математиков Лариса Львовна навсегда останется в памяти как соавтор легендарного задачника (Лавров, Максимова, "Задачи по теории множеств, математической логике и теории алгоритмов"; первое издание вышло в 1975 году), по которому и сегодня учатся студенты.

Светлая память.

➰ ВК

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

На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ

"Модальная и алгебраическая логика" и "Логические методы в информатике"

в ближайший вторник 8 апреля, начало в 18:30, состоится доклад

Докладчик:
Слюсарев Владислав Владимирович

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

Аннотация:
Для заданной модальной логики L формулы φ и ψ называются L-эквивалентными, если φ-ψ∈L. Модальная логика L называется локально табличной, если для любого n∈ω число классов L-эквивалентности модальных формул на n пропозициональных переменных конечно.

Критерий Сегерберга-Максимовой утверждает, что для одномодальных логик, расширяющих K4, локальная табличность эквивалентна конечной высоте. В общем случае этот критерий не выполнен, а аналоги неизвестны.

В этом докладе будут рассмотрены новые критерии, характеризующие локальную табличность произведений модальных логик. Произведение шкал Крипке F=(X,R) и G=(Y,S) определяется как шкала F*G=(X*Y,Rh,Rv), где
(a,b) Rh (c,d) ⟺ aRc и b=d;
(a,b) Rv (c,d) ⟺ a=c и bSd.
Произведением двух модальных логик называется логика класса шкал, состоящего из произведений шкал этих логик. Легко видеть, что локальная табличность обеих логик необходима, но не достаточна для локальной табличности их произведения. Для получения критерия мы описываем несколько синтаксических и семантических свойств, такие как: равномерная ограниченность сгустков одной из логик; свойство сокращения путей; конечность однопеременного фрагмента одной из логик.

Новые критерии позволяют найти ранее неизвестные семейства локально табличных бимодальных логик.

Доклад основан на совместной работе с И. Б. Шапировским. Препринт доступен по ссылке: http://arxiv.org/abs/2404.01670.

Видеозаписи предыдущих докладов:

https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX

Веб-страница с аннотациями и слайдами:

http://logic.math.msu.ru/sem/ml/

Для получения ссылки Zoom пишите на почту kudinov.andrey@gmail.com.
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!

➰ ВК

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

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

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

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

Докладчик: Иван Смирнов

Тема: Фрагменты арифметики и циклические выводы.

Аннотация:
Циклический вывод отличается от классического возможностью наличия циклов в "графе вывода", который для классического вывода является деревом. А. Симпсон [1] (и независимо С. Берарди и М. Татсута) доказал эквивалентность некоторой формальной системы арифметики 1-го порядка, основанной на циклических выводах, и арифметики Пеано.

В докладе мы расскажем о новой системе циклических выводов для арифметики 1-го порядка, предложенной в работе [2]. Глобальные ограничения корректности на выводы в этой системе выглядят проще, чем в предшествующих: задача проверки корректности вывода в ней лежит в классе P, а не только в PSPACE. Мы также определим некоторые фрагменты этой системы, основанные на ограничении сложности формул, входящих в вывод, эквивалентные известным фрагментам арифметики Пеано: $I \Sigma_n$ и $I \Sigma_n^R$.

Список литературы:
[1] A. Simpson. “Cyclic arithmetic is equivalent to Peano arithmetic”. In: FOSSACS 2017, Proceedings. pp. 283--300.
[2] L. Beklemishev, D. Shamkanov and I. Smirnov. "Fragments of arithmetic and cyclic proofs". arxiv.org/abs/2502.06639

➰ ВК

#матлог #не_мехмат

В ближайшие две среды, 9 и 16 апреля 2025 г., С.Л. Кузнецов прочитает две лекции в рамках курса «Coq» в Центральном университете.

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

На второй лекции будет рассказано о доказательстве непротиворечивости исчисления индуктивных конструкций (CIC — базовое исчисление системы Coq) в рамках теории множеств ZFC со счётным набором недостижимых кардиналов, а также обратное кодирование соответствующих расширений ZFC в Coq, по статье Б. Вернера 1997 г.

Место: учебный корпус Центрального университета, Москва, ул. Гашека, д. 7, аудитория F304 (3 этаж, из лифтов перейти по мосту и прямо)
Время: 9 и 16 апреля, 19:30

Для посещения нужно получить пропуск. Для этого нужно написать в телеграм Владу Пимкину @delamelicon, что идёте на лекцию С.Л.Кузнецова в среду. Желательно сделать это не позднее вторника.

➰ ВК

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

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

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

➰ ВК

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

🔥Возобновляет работу семинар "Некоторые применения математических методов в языкознании"! Это старейший семинар по математической лингвистике в России, одним из первых организаторов которого был Владимир Андреевич Успенский, в котором принимали участие Алексей Всеволодович Гладкий, Игорь Александрович Мельчук, Елена Викторовна Падучева и другие известные ученые. С 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

➰ ВК

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

Семинар «Вероятностные и субструктурные логические системы» (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/)

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

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

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

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
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

➰ ВК

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

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

Дата и время: 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 и др., верно обратное, т.е. точные и проективные формулы в этих логиках совпадают.

➰ ВК

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

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.

➰ ВК

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

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.

➰ ВК

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

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

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

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

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

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

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

➰ ВК

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

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

Дата, время и аудитория: 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 (лучше до этой среды включительно).

➰ ВК

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

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

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

📝 P_NP_2025

➰ ВК

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

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

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

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

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

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

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

➰ ВК

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

В пятницу 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) семантический анализ явлений, традиционно относимых к прагматике. А именно, преимущественно на материале русского языка, мы обсудим некоторые аргументы в пользу синтаксического представления речевых актов и модальный анализ перфектива (и, по возможности, некоторых других грамматических сущностей).

➰ ВК

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

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

➰ ВК