#матлог #учёба #просеминар
На занятии просеминара 21 ноября будет тема "Модальная логика" (Оноприенко А.А.).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 modal2024.pdf
➰ ВК
На занятии просеминара 21 ноября будет тема "Модальная логика" (Оноприенко А.А.).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 modal2024.pdf
➰ ВК
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
❤2👍1
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 22.11.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Дата и время: 22.11.2024 в 16:20
Докладчик: Артем Сергеевич Пиманов
Название: Современные модификации онтологических структур времени
Аннотация:
В рамках выступления рассматриваются предпосылки становления современных модификаций онтологических структур времени в контексте проблемы детерминизма.
Влияние представлений о детерминизме прослеживается в различных областях философии, в том числе и во временной логике. Рассмотрение ряда аспектов детерминизма позволяет подробно описать причины формирования в логике определенных подходов к оценке времененных высказываний. Так, в работе рассматривается анализ Артуром Прайором детерминистических аргументов, лежащих в основе классических вариантов семантики Оккамовского и Пирсового типов и принципа «жди и смотри». Дальнейшее изучение данных семантик по ряду логико-философских причин расходится на два самостоятельных и конкурирующих между собой направления: логику пространства-времени (BST) и гипотезу Thin Red Line. Эти системы представляют собой варианты оценки овремененных высказываний через использование пар момент, история, которые ввиду некоторых своих недостатков на текущий момент не завершены. Последнее побудило некоторых исследователей начать поиск альтернативных вариантов оценки. В частности, примечательны работы Джона Макфарлейна, где особое внимание уделяется определению условий адекватной препрезентации идеи открытого будущего. В его понимании ключевым условием является совмещение двух философских интуиций о детерминизме, которое можно реализовать за счет релятивизации оценки высказываний через контекст утверждения.
В дальнейшем на эти работы обратил внимание Томас Мюллер, который, занимаясь вопросом отображения локальных аспектов модальной упорядоченности (в том числе и с философской точки зрения), выдвинул идею семантики переходов. Ее развитие сегодня отражается в работах Антье Румберг, где предлагается вариант семантики с наличием оператора стабильности. Получившийся вариант семантики позволяет разрешить сразу несколько основных вопросов касательно детерминизма. В частности, наличие оператора стабильности позволяет показать специфический характер проявления высказываний о случайных событиях. В свою очередь, оценка высказываний позволяет точно и непротиворечиво реализовать предложенный Прайором принцип «жди и смотри». Но, на наш взгляд, такой вариант семантики имеет ряд проблем с описанными ранее представлениями о природе будущего.
🔗 Логика в Москве
➰ ВК
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 22.11.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Дата и время: 22.11.2024 в 16:20
Докладчик: Артем Сергеевич Пиманов
Название: Современные модификации онтологических структур времени
Аннотация:
В рамках выступления рассматриваются предпосылки становления современных модификаций онтологических структур времени в контексте проблемы детерминизма.
Влияние представлений о детерминизме прослеживается в различных областях философии, в том числе и во временной логике. Рассмотрение ряда аспектов детерминизма позволяет подробно описать причины формирования в логике определенных подходов к оценке времененных высказываний. Так, в работе рассматривается анализ Артуром Прайором детерминистических аргументов, лежащих в основе классических вариантов семантики Оккамовского и Пирсового типов и принципа «жди и смотри». Дальнейшее изучение данных семантик по ряду логико-философских причин расходится на два самостоятельных и конкурирующих между собой направления: логику пространства-времени (BST) и гипотезу Thin Red Line. Эти системы представляют собой варианты оценки овремененных высказываний через использование пар момент, история, которые ввиду некоторых своих недостатков на текущий момент не завершены. Последнее побудило некоторых исследователей начать поиск альтернативных вариантов оценки. В частности, примечательны работы Джона Макфарлейна, где особое внимание уделяется определению условий адекватной препрезентации идеи открытого будущего. В его понимании ключевым условием является совмещение двух философских интуиций о детерминизме, которое можно реализовать за счет релятивизации оценки высказываний через контекст утверждения.
В дальнейшем на эти работы обратил внимание Томас Мюллер, который, занимаясь вопросом отображения локальных аспектов модальной упорядоченности (в том числе и с философской точки зрения), выдвинул идею семантики переходов. Ее развитие сегодня отражается в работах Антье Румберг, где предлагается вариант семантики с наличием оператора стабильности. Получившийся вариант семантики позволяет разрешить сразу несколько основных вопросов касательно детерминизма. В частности, наличие оператора стабильности позволяет показать специфический характер проявления высказываний о случайных событиях. В свою очередь, оценка высказываний позволяет точно и непротиворечиво реализовать предложенный Прайором принцип «жди и смотри». Но, на наш взгляд, такой вариант семантики имеет ряд проблем с описанными ранее представлениями о природе будущего.
🔗 Логика в Москве
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
👍1
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Nov 25, 2024. Time: 18:30 (MSK), 16:30 (CET)
Title: Word combinatorics and approximations of reals
(Following Matthieu Rosenfeld, LIRMM)
Let $\alpha$ be a real number that we try to approximate by rational numbers $m/n$. It can be done with arbitrary precision, but there is a tradeoff between the precision and the denominator. For given denominator $n$ we can obviously make the error smaller than $0.5/n$ (by rounding $\alpha n$); Dirichlet theorem says that for _some_ n the precision could be much better. Let us an approximation $\eps$-good if $|\alpha n -m|\le\eps$. So for every $n$ there is $1/2$-good approximation with denominator $n$ (obvious), and for every $\eps0$ there are infinitely many denominators that allow $\eps$-good approximations (Dirichlet)
What if we allow only some denominators? Then Dirichlet theorem is no more true. For example, if we allow only denominators $1,2,4,8,16,\ldots$, then $1/3$ = $0.0101010101\ldots$ in binary, has no $1/4$-good approximations ($n\alpha$ has fractional part $1/3$ or $2/3$).
Question: assume that we have some other sequence of denominators $n_1,n_2,\ldots$ that is sparse: $n_i2n_{i-1}$, and some $\eps0$. Is it always possible to find some $\alpha$ that has no $\eps$-good approximations, for some $\eps$ and for all the denominators in the sequence? (Note that we cannot take $\alpha$ randomly, since for every $\eps$ the probability of success in $2\eps$ and the union bound does not work for infinitely many denominators.)
People in number theory were interested in this question (and finally proved that the statement is true). Matthieu Rosenfeld noted that we can get a simple proof of this result if we use tools from word combinatorics (e.g., Joe Miller's potential argument for avoiding forbidden strings). This proof will be explained.
➰ ВК
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Nov 25, 2024. Time: 18:30 (MSK), 16:30 (CET)
Title: Word combinatorics and approximations of reals
(Following Matthieu Rosenfeld, LIRMM)
Let $\alpha$ be a real number that we try to approximate by rational numbers $m/n$. It can be done with arbitrary precision, but there is a tradeoff between the precision and the denominator. For given denominator $n$ we can obviously make the error smaller than $0.5/n$ (by rounding $\alpha n$); Dirichlet theorem says that for _some_ n the precision could be much better. Let us an approximation $\eps$-good if $|\alpha n -m|\le\eps$. So for every $n$ there is $1/2$-good approximation with denominator $n$ (obvious), and for every $\eps0$ there are infinitely many denominators that allow $\eps$-good approximations (Dirichlet)
What if we allow only some denominators? Then Dirichlet theorem is no more true. For example, if we allow only denominators $1,2,4,8,16,\ldots$, then $1/3$ = $0.0101010101\ldots$ in binary, has no $1/4$-good approximations ($n\alpha$ has fractional part $1/3$ or $2/3$).
Question: assume that we have some other sequence of denominators $n_1,n_2,\ldots$ that is sparse: $n_i2n_{i-1}$, and some $\eps0$. Is it always possible to find some $\alpha$ that has no $\eps$-good approximations, for some $\eps$ and for all the denominators in the sequence? (Note that we cannot take $\alpha$ randomly, since for every $\eps$ the probability of success in $2\eps$ and the union bound does not work for infinitely many denominators.)
People in number theory were interested in this question (and finally proved that the statement is true). Matthieu Rosenfeld noted that we can get a simple proof of this result if we use tools from word combinatorics (e.g., Joe Miller's potential argument for avoiding forbidden strings). This proof will be explained.
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
👍2
#матлог #учёба #просеминар
На занятии просеминара 28 ноября будет тема "Доказуемо рекурсивные функции и теорема Гёделя" (Беклемишев Л.Д.).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
➰ ВК
На занятии просеминара 28 ноября будет тема "Доказуемо рекурсивные функции и теорема Гёделя" (Беклемишев Л.Д.).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
➰ ВК
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
❤1👍1
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 27 ноября.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.
Заседание пройдет очно без трансляции.
Докладчик: Стас Кикоть
Название: О монотонной определенности и переписываемости рекурсивных запросов относительно представлений
Аннотация:
Запрос Q монотонно определен относительно представления базы данных V, если Q можно выразить как монотонную функцию от таблиц представления. В случае представлений и запросов из реляционной алгебры монотонная определенность совпадает с переписываемостью в виде объединения конъюнктивных запросов и разрешима в важных частных случаях. В докладе речь пойдет о положении вещей для представлений и запросов в рекурсивном языке запросов Datalog и его фрагментах. Будут приведены как положительные, так и отрицательные результаты о разрешимости монотонной определенности, а также о совпадении монотонной определенности с переписываемостью в Datalog.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 27 ноября.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.
Заседание пройдет очно без трансляции.
Докладчик: Стас Кикоть
Название: О монотонной определенности и переписываемости рекурсивных запросов относительно представлений
Аннотация:
Запрос Q монотонно определен относительно представления базы данных V, если Q можно выразить как монотонную функцию от таблиц представления. В случае представлений и запросов из реляционной алгебры монотонная определенность совпадает с переписываемостью в виде объединения конъюнктивных запросов и разрешима в важных частных случаях. В докладе речь пойдет о положении вещей для представлений и запросов в рекурсивном языке запросов Datalog и его фрагментах. Будут приведены как положительные, так и отрицательные результаты о разрешимости монотонной определенности, а также о совпадении монотонной определенности с переписываемостью в Datalog.
➰ ВК
Яндекс Карты
МФТИ, радиотехнический корпус: как доехать на автомобиле, общественным транспортом или пешком – Яндекс Карты
МФТИ, радиотехнический корпус: варианты маршрутов с указанием расстояния и времени в пути. Яндекс Карты покажут, как добраться до нужного места на разных видах транспорта или пешком.
👍2
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 29.11.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Дата и время: 29.11.2024 в 16:20
Докладчик: С.П.Одинцов
Название: Слабо импликативные логики: подходы к определению дефинициальной эквивалентности и определимости.
Аннотация:
В логиках с сильным отрицанием ∼ условия истинности и ложности формул определяются параллельно, а сильное отрицание позволяет переходить от условий истинности к условиям ложности и наоборот. При этом истинность слабой эквивалентности φ ↔ ψ, определяемой обычным образом, означает лишь, что в каждом из возможных миров формулы φ и ψ одновременно истинны. Сильная эквивалентность φ = ψ := (φ ↔ ψ)∧(∼φ ↔ ∼ψ) сохраняет как истинность, так и ложность формул и является конгруэнцией на алгебре формул. Поэтому имеет смысл различать сильные (=) и слабые (↔) версии таких понятий как дефинициальная эквивалентность логик, явная и неявная определимость параметров.
Импликативные логики Фонта - это класс логик с импликацией в языке, допускающих "стандартную" алгебраизацию. В докладе будет введен класс слабо импликативных логик (си-логик) в языке с импликацией и сильным отрицанием. Такие логики являются естественной модификацией импликативных логик и включают практически все известные примеры логик с сильным отрицанием. Далее мы определим понятие слабой дефинициальной эквивалентности для си-логик, сделаем обзор различных подходов к определению Белнаповских модальных логик и покажем, что эти подходы приводят к слабо дефинициально эквивалентным логикам. В классе си-логик будет выделен подкласс логик, обобщающих логики основанные на бирешетках и показано, что для логик этого класса пропадает разница между слабой и сильной версиями дефинициальной эквивалентности.
Известная теорема Крайзеля утверждает, что любая суперинтуиционистская логика обладает свойством Бета, т.е. в каждой из таких логик неявная определимость влечет явную. Мы заметим, что эта теорема легко обобщается на произвольные импликативные логики. А для избыточных слабоимпликативных логик, удовлетворяющих теореме дедукции, из сильной неявной определимости следует слабая явная определимость. К числу избыточных слабоимпликативных логик с теоремой дедукции относятся, например, все расширения избыточной логики Нельсона N3.
🔗 Логика в Москве
➰ ВК
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 29.11.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Дата и время: 29.11.2024 в 16:20
Докладчик: С.П.Одинцов
Название: Слабо импликативные логики: подходы к определению дефинициальной эквивалентности и определимости.
Аннотация:
В логиках с сильным отрицанием ∼ условия истинности и ложности формул определяются параллельно, а сильное отрицание позволяет переходить от условий истинности к условиям ложности и наоборот. При этом истинность слабой эквивалентности φ ↔ ψ, определяемой обычным образом, означает лишь, что в каждом из возможных миров формулы φ и ψ одновременно истинны. Сильная эквивалентность φ = ψ := (φ ↔ ψ)∧(∼φ ↔ ∼ψ) сохраняет как истинность, так и ложность формул и является конгруэнцией на алгебре формул. Поэтому имеет смысл различать сильные (=) и слабые (↔) версии таких понятий как дефинициальная эквивалентность логик, явная и неявная определимость параметров.
Импликативные логики Фонта - это класс логик с импликацией в языке, допускающих "стандартную" алгебраизацию. В докладе будет введен класс слабо импликативных логик (си-логик) в языке с импликацией и сильным отрицанием. Такие логики являются естественной модификацией импликативных логик и включают практически все известные примеры логик с сильным отрицанием. Далее мы определим понятие слабой дефинициальной эквивалентности для си-логик, сделаем обзор различных подходов к определению Белнаповских модальных логик и покажем, что эти подходы приводят к слабо дефинициально эквивалентным логикам. В классе си-логик будет выделен подкласс логик, обобщающих логики основанные на бирешетках и показано, что для логик этого класса пропадает разница между слабой и сильной версиями дефинициальной эквивалентности.
Известная теорема Крайзеля утверждает, что любая суперинтуиционистская логика обладает свойством Бета, т.е. в каждой из таких логик неявная определимость влечет явную. Мы заметим, что эта теорема легко обобщается на произвольные импликативные логики. А для избыточных слабоимпликативных логик, удовлетворяющих теореме дедукции, из сильной неявной определимости следует слабая явная определимость. К числу избыточных слабоимпликативных логик с теоремой дедукции относятся, например, все расширения избыточной логики Нельсона N3.
🔗 Логика в Москве
➰ ВК
👍2
#матлог #учёба #спецсеминар
Ближайший семинар «Категориальные грамматики» состоится 28 ноября (28.11.2024).
Начало: 18:30. Аудитория: 424.
Докладчик: Т.Г. Пшеницын
Тема: ''Операции вставки на формальных языках: от простого к сложному''
В данном обзорном докладе будет рассмотрена классическая операция на формальных языках — вставка — и её разновидности. Стандартный вариант этой операции языкам L и M ставит в соответствие множество слов {uyv|uv из L, y из M}. В литературе также изучаются контекстные вставки: например, когда зафиксировано (конечное) множество контекстов C (состоящее из пар слов), и вставка слова возможна только между строками z и t, пара из которых принадлежит C. Есть ещё более хитрая сайт-направленная вставка, которая языкам L и M ставит в соответствие язык {uzytv|uztv из L, zyt из M}; это тоже контекстная вставка, однако контексты z и t здесь определяются не внешним образом, с помощью фиксированного множества C, а внутренним.
Контекстные вставки изначально мотивировались лингвистическими приложениями (например, в работе Галюкшова "Полуконтекстные грамматики" 1981 года), а позднее — приложениями в биоинформатике: если рассматривать молекулы ДНК как слова, то их взаимодействие действительно можно моделировать контекстной вставкой.
В докладе будет рассказано об избранных свойствах вставок. В частности, планируется показать конструкцию полуконтекстной грамматики Галюкшова, порождающей язык, не являющийся контекстно-свободным (и даже полулинейным). В конце доклада предполагается описать текущую работу автора в данном направлении и один из результатов: существует конечный язык, замыкание которого относительно сайт-направленной вставки не является контекстно-свободным.
➰ ВК
Ближайший семинар «Категориальные грамматики» состоится 28 ноября (28.11.2024).
Начало: 18:30. Аудитория: 424.
Докладчик: Т.Г. Пшеницын
Тема: ''Операции вставки на формальных языках: от простого к сложному''
В данном обзорном докладе будет рассмотрена классическая операция на формальных языках — вставка — и её разновидности. Стандартный вариант этой операции языкам L и M ставит в соответствие множество слов {uyv|uv из L, y из M}. В литературе также изучаются контекстные вставки: например, когда зафиксировано (конечное) множество контекстов C (состоящее из пар слов), и вставка слова возможна только между строками z и t, пара из которых принадлежит C. Есть ещё более хитрая сайт-направленная вставка, которая языкам L и M ставит в соответствие язык {uzytv|uztv из L, zyt из M}; это тоже контекстная вставка, однако контексты z и t здесь определяются не внешним образом, с помощью фиксированного множества C, а внутренним.
Контекстные вставки изначально мотивировались лингвистическими приложениями (например, в работе Галюкшова "Полуконтекстные грамматики" 1981 года), а позднее — приложениями в биоинформатике: если рассматривать молекулы ДНК как слова, то их взаимодействие действительно можно моделировать контекстной вставкой.
В докладе будет рассказано об избранных свойствах вставок. В частности, планируется показать конструкцию полуконтекстной грамматики Галюкшова, порождающей язык, не являющийся контекстно-свободным (и даже полулинейным). В конце доклада предполагается описать текущую работу автора в данном направлении и один из результатов: существует конечный язык, замыкание которого относительно сайт-направленной вставки не является контекстно-свободным.
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #спецсеминар
Ближайший семинар «Категориальные грамматики» состоится 7 ноября ... Смотрите полностью ВКонтакте.
Ближайший семинар «Категориальные грамматики» состоится 7 ноября ... Смотрите полностью ВКонтакте.
❤5
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Logic Online Seminar (https://www.mathnet.ru/conf876)
Monday 16:00 MSK (UTC+3), Room 313 MIAN + Zoom (online talk)
02.12.2024 Wei Wang (Sun Yat-sen University, Guangzhou): Definable Combinatorial Principles in Fragments of Arithmetic (online only)
In fragments of arithmetic, the pigeonhole principle may fail for definable partitions of finite sets. Dimicoupolous and Paris proved that over IΣ_1 the ordinary pigeonhole principle for Σ_n+1 partitions is equivalent to BΣ_n+1 (n0). Later Kaye formulated several second order pigeonhole principles which are used to axiomatise κ-like models of arithmetic. A first order fragment derived from one of Kaye's pigeonhole principles, known as
Σ_n-cardinality scheme or CΣ_n, has interesting independence properties proved by Kaye himself and also proved useful in reverse mathematics. Recently, we study another first order fragment of these pigeonhole principles, called Generalised Pigeonhole Principle (GPHP) by Kaye. We shall introduce some progress concerning Σ_n+1-GPHP from perspectives of both first order arithmetic and reverse mathematics.
🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&
➰ ВК
Logic Online Seminar (https://www.mathnet.ru/conf876)
Monday 16:00 MSK (UTC+3), Room 313 MIAN + Zoom (online talk)
02.12.2024 Wei Wang (Sun Yat-sen University, Guangzhou): Definable Combinatorial Principles in Fragments of Arithmetic (online only)
In fragments of arithmetic, the pigeonhole principle may fail for definable partitions of finite sets. Dimicoupolous and Paris proved that over IΣ_1 the ordinary pigeonhole principle for Σ_n+1 partitions is equivalent to BΣ_n+1 (n0). Later Kaye formulated several second order pigeonhole principles which are used to axiomatise κ-like models of arithmetic. A first order fragment derived from one of Kaye's pigeonhole principles, known as
Σ_n-cardinality scheme or CΣ_n, has interesting independence properties proved by Kaye himself and also proved useful in reverse mathematics. Recently, we study another first order fragment of these pigeonhole principles, called Generalised Pigeonhole Principle (GPHP) by Kaye. We shall introduce some progress concerning Σ_n+1-GPHP from perspectives of both first order arithmetic and reverse mathematics.
🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&
➰ ВК
👍1
#матлог #отмены
В связи с болезнью докладчика доклад на НИС "Современные проблемы математической логики" в ВШЭ отменяется.
(https://vk.com/wall-70743963_1833)
Ждем вас в следующую пятницу!
➰ ВК
В связи с болезнью докладчика доклад на НИС "Современные проблемы математической логики" в ВШЭ отменяется.
(https://vk.com/wall-70743963_1833)
Ждем вас в следующую пятницу!
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
👍1
#матлог #учёба #просеминар
На занятии просеминара 5 декабря будет тема "Деревья решений и вопросная сложность" (Н.К.Верещагин).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 Деревья решений и вопросная сложность 2024.pdf
➰ ВК
На занятии просеминара 5 декабря будет тема "Деревья решений и вопросная сложность" (Н.К.Верещагин).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 Деревья решений и вопросная сложность 2024.pdf
➰ ВК
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
👍1
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 2, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Ivan Baburin
Title: Orphans in Cellular Automata
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. Every non-surjective cellular automaton A has so-called Garden-of-Eden configurations, i.e. configurations which can never naturally appear in the evolution of A because they don’t have a preimage. It turns out that it is possible to characterize all Garden-of-Eden configurations in a cellular automaton using only finite patterns and regular languages. In this talk we discuss the following results, based on the presentation in [1]:
1. The duality between Garden-of-Eden configurations and orphans (finite patterns without a preimage). Every Garden-of-Eden configuration needs to contain an orphan, and every configuration containing an orphan is Garden-of-Eden.
2. For any one-dimensional cellular automaton the set of all orphans forms a regular language, and this language can be recognized using a finite-state machine constructed from a de Brujin graph.
Further Reading
The presented algorithms and dualities with de Brujin graphs were originally discovered in [2], and they can be further generalized to test for injectivity and surjectivity of one-dimensional cellular automata. A generalization to higher dimensions is impossible, since these properties are known to be undecidable [3].
References
1. J. Kari, Cellular automata. University of Turku, 2022.
2. K. Sutner, “De bruijn graphs and linear cellular automata,” Complex Systems, vol. 5, no. 1, pp. 19–30, 1991.
3. J. Kari, “Theory of cellular autom
➰ ВК
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 2, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Ivan Baburin
Title: Orphans in Cellular Automata
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. Every non-surjective cellular automaton A has so-called Garden-of-Eden configurations, i.e. configurations which can never naturally appear in the evolution of A because they don’t have a preimage. It turns out that it is possible to characterize all Garden-of-Eden configurations in a cellular automaton using only finite patterns and regular languages. In this talk we discuss the following results, based on the presentation in [1]:
1. The duality between Garden-of-Eden configurations and orphans (finite patterns without a preimage). Every Garden-of-Eden configuration needs to contain an orphan, and every configuration containing an orphan is Garden-of-Eden.
2. For any one-dimensional cellular automaton the set of all orphans forms a regular language, and this language can be recognized using a finite-state machine constructed from a de Brujin graph.
Further Reading
The presented algorithms and dualities with de Brujin graphs were originally discovered in [2], and they can be further generalized to test for injectivity and surjectivity of one-dimensional cellular automata. A generalization to higher dimensions is impossible, since these properties are known to be undecidable [3].
References
1. J. Kari, Cellular automata. University of Turku, 2022.
2. K. Sutner, “De bruijn graphs and linear cellular automata,” Complex Systems, vol. 5, no. 1, pp. 19–30, 1991.
3. J. Kari, “Theory of cellular autom
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 4 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Михаил Рыбаков
Название: Алгоритмическая неразрешимость логики квазиарных предикатов
Аннотация:
Логика квазиарных предикатов предполагает, что язык содержит предикатные буквы, арность которых «варьируется»: в моделях значение предиката определяется на наборе значений сразу всех переменных языка, при этом допускается, что некоторые переменные значений не получили. Такой подход имеет «компьютерную» мотивацию, когда, во-первых, значения у некоторых переменных могу отсутствовать (при выполнении программы), а во-вторых, число элементов, находящихся (или не находящихся) в интересующем нас отношении, может варьироваться (например, когда мы рассматриваем конечный список элементов и требуем его упорядоченность в смысле некоторого предопределённого порядка). Изучением подобных систем занимались М.Никитченко, С.Шкильняк, В.Тимофеев. В частности, было построено погружение многосортной логики квазиарных предикатов в многосортную классическую логику предикатов. В докладе будет показано, как построить погружение классической логики предикатов в логику квазиарных предикатов (уже для односортного случая). При этом для опровержимости перевода исходной формулы будет использоваться модель с тем же носителем, поэтому фактически будет построено и погружение логики конечных моделей в расширение логики квазиарных предикатов, определяемое конечными моделями.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 4 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Михаил Рыбаков
Название: Алгоритмическая неразрешимость логики квазиарных предикатов
Аннотация:
Логика квазиарных предикатов предполагает, что язык содержит предикатные буквы, арность которых «варьируется»: в моделях значение предиката определяется на наборе значений сразу всех переменных языка, при этом допускается, что некоторые переменные значений не получили. Такой подход имеет «компьютерную» мотивацию, когда, во-первых, значения у некоторых переменных могу отсутствовать (при выполнении программы), а во-вторых, число элементов, находящихся (или не находящихся) в интересующем нас отношении, может варьироваться (например, когда мы рассматриваем конечный список элементов и требуем его упорядоченность в смысле некоторого предопределённого порядка). Изучением подобных систем занимались М.Никитченко, С.Шкильняк, В.Тимофеев. В частности, было построено погружение многосортной логики квазиарных предикатов в многосортную классическую логику предикатов. В докладе будет показано, как построить погружение классической логики предикатов в логику квазиарных предикатов (уже для односортного случая). При этом для опровержимости перевода исходной формулы будет использоваться модель с тем же носителем, поэтому фактически будет построено и погружение логики конечных моделей в расширение логики квазиарных предикатов, определяемое конечными моделями.
➰ ВК
Яндекс Карты
МФТИ, радиотехнический корпус: как доехать на автомобиле, общественным транспортом или пешком – Яндекс Карты
МФТИ, радиотехнический корпус: варианты маршрутов с указанием расстояния и времени в пути. Яндекс Карты покажут, как добраться до нужного места на разных видах транспорта или пешком.
#матлог #не_мехмат
We wish to invite you to an AMR-RMA lecture by Alexander Razborov (University of Chicago and Steklov Institute), a renowned mathematician and computer scientist. This is a colloquium-type talk for a general mathematical audience.
Title: Continuous Combinatorics
The lecture will take place via Zoom on Thursday next week, December 5, at 18:00 Israel time. For receive the zoom link, please email alexander.shen@lirmm.fr.
➰ ВК
We wish to invite you to an AMR-RMA lecture by Alexander Razborov (University of Chicago and Steklov Institute), a renowned mathematician and computer scientist. This is a colloquium-type talk for a general mathematical audience.
Title: Continuous Combinatorics
The lecture will take place via Zoom on Thursday next week, December 5, at 18:00 Israel time. For receive the zoom link, please email alexander.shen@lirmm.fr.
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #не_мехмат
We wish to invite you to an AMR-RMA lecture by Alexander Razborov (Univers... Смотрите полностью ВКонтакте.
We wish to invite you to an AMR-RMA lecture by Alexander Razborov (Univers... Смотрите полностью ВКонтакте.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 06.12.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Докладчик: С.П.Одинцов
Название: Слабо импликативные логики: подходы к определению дефинициальной эквивалентности и определимости.
Аннотация:
В логиках с сильным отрицанием ∼ условия истинности и ложности формул определяются параллельно, а сильное отрицание позволяет переходить от условий истинности к условиям ложности и наоборот. При этом истинность слабой эквивалентности φ ↔ ψ, определяемой обычным образом, означает лишь, что в каждом из возможных миров формулы φ и ψ одновременно истинны. Сильная эквивалентность φ = ψ := (φ ↔ ψ)∧(∼φ ↔ ∼ψ) сохраняет как истинность, так и ложность формул и является конгруэнцией на алгебре формул. Поэтому имеет смысл различать сильные (=) и слабые (↔) версии таких понятий как дефинициальная эквивалентность логик, явная и неявная определимость параметров.
Импликативные логики Фонта - это класс логик с импликацией в языке, допускающих "стандартную" алгебраизацию. В докладе будет введен класс слабо импликативных логик (си-логик) в языке с импликацией и сильным отрицанием. Такие логики являются естественной модификацией импликативных логик и включают практически все известные примеры логик с сильным отрицанием. Далее мы определим понятие слабой дефинициальной эквивалентности для си-логик, сделаем обзор различных подходов к определению Белнаповских модальных логик и покажем, что эти подходы приводят к слабо дефинициально эквивалентным логикам. В классе си-логик будет выделен подкласс логик, обобщающих логики основанные на бирешетках и показано, что для логик этого класса пропадает разница между слабой и сильной версиями дефинициальной эквивалентности.
Известная теорема Крайзеля утверждает, что любая суперинтуиционистская логика обладает свойством Бета, т.е. в каждой из таких логик неявная определимость влечет явную. Мы заметим, что эта теорема легко обобщается на произвольные импликативные логики. А для избыточных слабоимпликативных логик, удовлетворяющих теореме дедукции, из сильной неявной определимости следует слабая явная определимость. К числу избыточных слабоимпликативных логик с теоремой дедукции относятся, например, все расширения избыточной логики Нельсона N3.
🔗 Логика в Москве
➰ ВК
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 06.12.2024 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Докладчик: С.П.Одинцов
Название: Слабо импликативные логики: подходы к определению дефинициальной эквивалентности и определимости.
Аннотация:
В логиках с сильным отрицанием ∼ условия истинности и ложности формул определяются параллельно, а сильное отрицание позволяет переходить от условий истинности к условиям ложности и наоборот. При этом истинность слабой эквивалентности φ ↔ ψ, определяемой обычным образом, означает лишь, что в каждом из возможных миров формулы φ и ψ одновременно истинны. Сильная эквивалентность φ = ψ := (φ ↔ ψ)∧(∼φ ↔ ∼ψ) сохраняет как истинность, так и ложность формул и является конгруэнцией на алгебре формул. Поэтому имеет смысл различать сильные (=) и слабые (↔) версии таких понятий как дефинициальная эквивалентность логик, явная и неявная определимость параметров.
Импликативные логики Фонта - это класс логик с импликацией в языке, допускающих "стандартную" алгебраизацию. В докладе будет введен класс слабо импликативных логик (си-логик) в языке с импликацией и сильным отрицанием. Такие логики являются естественной модификацией импликативных логик и включают практически все известные примеры логик с сильным отрицанием. Далее мы определим понятие слабой дефинициальной эквивалентности для си-логик, сделаем обзор различных подходов к определению Белнаповских модальных логик и покажем, что эти подходы приводят к слабо дефинициально эквивалентным логикам. В классе си-логик будет выделен подкласс логик, обобщающих логики основанные на бирешетках и показано, что для логик этого класса пропадает разница между слабой и сильной версиями дефинициальной эквивалентности.
Известная теорема Крайзеля утверждает, что любая суперинтуиционистская логика обладает свойством Бета, т.е. в каждой из таких логик неявная определимость влечет явную. Мы заметим, что эта теорема легко обобщается на произвольные импликативные логики. А для избыточных слабоимпликативных логик, удовлетворяющих теореме дедукции, из сильной неявной определимости следует слабая явная определимость. К числу избыточных слабоимпликативных логик с теоремой дедукции относятся, например, все расширения избыточной логики Нельсона N3.
🔗 Логика в Москве
➰ ВК
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 9, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Andrey Storozhenko, UCLA
Title: The communication complexity of approximating matrix rank
Alice and Bob have on input two n times n matrices A and B, respectively. They want to compute or, at least, approximate the rank of the sum of their matrices A + B. The talk will be devoted to the communication complexity of this task and its applications for the problem of approximating the rank of a matrix by streaming algorithms.
The paper:
https://www.computer.org/csdl/proceedings-article/focs/2024/167400a433/22gEX3OxrJS
🔗 CSDL | IEEE Computer Society
➰ ВК
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 9, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Andrey Storozhenko, UCLA
Title: The communication complexity of approximating matrix rank
Alice and Bob have on input two n times n matrices A and B, respectively. They want to compute or, at least, approximate the rank of the sum of their matrices A + B. The talk will be devoted to the communication complexity of this task and its applications for the problem of approximating the rank of a matrix by streaming algorithms.
The paper:
https://www.computer.org/csdl/proceedings-article/focs/2024/167400a433/22gEX3OxrJS
🔗 CSDL | IEEE Computer Society
➰ ВК
#матлог
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
6 декабря (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия"
Тема доклада: "К вопросу о значении автореферентности для онтологического аргумента"
Докладчик: Данияр Шамканов (НИУ ВШЭ)
Ждём вас в кабинете А121 или в Zoom!
Анонс: https://llfp.hse.ru/announcements/993289661.html
➰ ВК
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
6 декабря (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия"
Тема доклада: "К вопросу о значении автореферентности для онтологического аргумента"
Докладчик: Данияр Шамканов (НИУ ВШЭ)
Ждём вас в кабинете А121 или в Zoom!
Анонс: https://llfp.hse.ru/announcements/993289661.html
➰ ВК
🔥3
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 11 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Валентин Борисович Шехтман
Название: Квадраты Сегерберга модальных логик
Аннотация.
В работе 1973 г. Кристер Сегерберг ввел 2-мерную модальную логику B, эквивалентную фрагменту классической логики предикатов с 2 переменными. Для нее он построил конечную аксиоматику и доказал финитную аппроксимируемость. Обобщения этой логики (квадраты Сегерберга) рассматривались докладчиком в статьях 2011-2012 и 2018 гг. Квадраты Сегерберга во многих случаях погружаются в классическую логику предикатов с 3 переменными, и для них также удалось доказать конечную аксиоматизируемость и финитную аппроксимируемость. В доказательствах использовались логические игры.
В докладе будет дан обзор известных на сегодня результатов и открытых проблем о квадратах Сегерберга.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 11 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Валентин Борисович Шехтман
Название: Квадраты Сегерберга модальных логик
Аннотация.
В работе 1973 г. Кристер Сегерберг ввел 2-мерную модальную логику B, эквивалентную фрагменту классической логики предикатов с 2 переменными. Для нее он построил конечную аксиоматику и доказал финитную аппроксимируемость. Обобщения этой логики (квадраты Сегерберга) рассматривались докладчиком в статьях 2011-2012 и 2018 гг. Квадраты Сегерберга во многих случаях погружаются в классическую логику предикатов с 3 переменными, и для них также удалось доказать конечную аксиоматизируемость и финитную аппроксимируемость. В доказательствах использовались логические игры.
В докладе будет дан обзор известных на сегодня результатов и открытых проблем о квадратах Сегерберга.
➰ ВК
Яндекс Карты
МФТИ, радиотехнический корпус: как доехать на автомобиле, общественным транспортом или пешком – Яндекс Карты
МФТИ, радиотехнический корпус: варианты маршрутов с указанием расстояния и времени в пути. Яндекс Карты покажут, как добраться до нужного места на разных видах транспорта или пешком.
🔥2
#матлог #учёба #просеминар
На занятии просеминара 12 декабря (последнем в 2024 году) будет продолжение темы "Деревья решений и вопросная сложность" (Н.К.Верещагин).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 Деревья решений и вопросная сложность 2024.pdf
➰ ВК
На занятии просеминара 12 декабря (последнем в 2024 году) будет продолжение темы "Деревья решений и вопросная сложность" (Н.К.Верещагин).
Можно заранее порешать задачи (прикреплены к посту).
❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо
📝 Деревья решений и вопросная сложность 2024.pdf
➰ ВК
Telegram
Просеминар по математической логике и информатике
Ansi Diana invites you to join this group on Telegram.
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Logic Online Seminar (https://www.mathnet.ru/conf876) совместно с семинаром С.И. Адяна
понедельник 16:00 MSK (UTC+3), ауд. 313 МИАН + Контур Толк
16.12.2024 А.Я. Канель-Белов (Бар-Илан, МФТИ, МГУ, https://www.mathnet.ru/rus/person8698): Алгоритмическая неразрешимость проблемы вложения алгебраических многообразий (очный)
Чрезвычайно интересной и фундаментальной является задача об алгоритмической разрешимости проверки наличия изоморфизма между двумя алгебраическими многообразиями. Родственной и более простой задачей является задача о вложимости. В общем виде она формулируется так: пусть A и B – два алгебраических многообразия; определить, существует ли вложение A в B, найти алгоритм или доказать его отсутствие. Доклад посвящен отрицательному решению данного вопроса для аффинных многообразий над алгебраически замкнутым полем характеристики не 2, чьи координатные кольца заданы образующими и определяющими соотношениями.
🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&
➰ ВК
Logic Online Seminar (https://www.mathnet.ru/conf876) совместно с семинаром С.И. Адяна
понедельник 16:00 MSK (UTC+3), ауд. 313 МИАН + Контур Толк
16.12.2024 А.Я. Канель-Белов (Бар-Илан, МФТИ, МГУ, https://www.mathnet.ru/rus/person8698): Алгоритмическая неразрешимость проблемы вложения алгебраических многообразий (очный)
Чрезвычайно интересной и фундаментальной является задача об алгоритмической разрешимости проверки наличия изоморфизма между двумя алгебраическими многообразиями. Родственной и более простой задачей является задача о вложимости. В общем виде она формулируется так: пусть A и B – два алгебраических многообразия; определить, существует ли вложение A в B, найти алгоритм или доказать его отсутствие. Доклад посвящен отрицательному решению данного вопроса для аффинных многообразий над алгебраически замкнутым полем характеристики не 2, чьи координатные кольца заданы образующими и определяющими соотношениями.
🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&
➰ ВК
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 16, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Andrey Storozhenko, UCLA
Title: The communication complexity of approximating matrix rank (sequel)
It was shown that if Alice and Bob have n times n matrices A and B over a finite field, then deciding, if A + B have full rank requires n^2 log |F| bits, for deterministic protocols. Next time there will be a lower bound against randomized protocols (and probably for the approximate version of the problem).
➰ ВК
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
Date: Dec 16, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Andrey Storozhenko, UCLA
Title: The communication complexity of approximating matrix rank (sequel)
It was shown that if Alice and Bob have n times n matrices A and B over a finite field, then deciding, if A + B have full rank requires n^2 log |F| bits, for deterministic protocols. Next time there will be a lower bound against randomized protocols (and probably for the approximate version of the problem).
➰ ВК
VK
Кафедра математической логики МГУ. Запись со стены.
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
Kolmogorov seminar on complexity (for receive the zoom link, plea... Смотрите полностью ВКонтакте.
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на последний в 2024 году логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 18 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Андрей Кудинов
Название: О сохранение сложности слаботранзитивных модальных логик с универсальной модальностью при добавлении аксиомы связности.
Аннотация.
Под сложностью проблемы выполнимости некоторой модальной логики L понимается сложность следующей массовой задачи: по данной формуле A определить, выполнима ли формула A на некоторой шкале логики L. Эта задача является двойственной к задачи выводимости в логике, т.к. формула A выводима в L тогда и только тогда, когда формула \lnot A невыполнима на L-шкале. Сложностной класс PSPACE содержит все массовые задачи, которые можно решить на машине Тьюринга, которая использует не больше полинома от длины входа ячеек ленты в процессе выполнения.
Мы будем рассматривать слаботранзитивные логики, т.е. логики содержащие wK4 = K + \Box p \land p \to \Box \Box p.
Общезначимость этой логики соответствует тому, что рефлексивное замыкание отношения - транзитивно.
Добавление универсальной модальности увеличивает выразительную силу языка. Добавление универсальной модальности рассматривалось в 90-е годы в работах Горанко и Пасси, а в работе Шехтмана было доказано, что в языке с универсальной модальностью можно выразить связность.
Мы покажем, что если проблема выполнимости для логики с универсальной модальностью некоторого класса слаботранзитивных шкал содержится в сложностном классе PSPACE, то добавление к этой логике аксиомы связности не выведет из класса PSPACE.
➰ ВК
Уважаемые коллеги, приглашаем вас на последний в 2024 году логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 18 декабря.
Время проведения семинара 14:30.
МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный
Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16
В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.
Заседание пройдет очно без трансляции.
Докладчик: Андрей Кудинов
Название: О сохранение сложности слаботранзитивных модальных логик с универсальной модальностью при добавлении аксиомы связности.
Аннотация.
Под сложностью проблемы выполнимости некоторой модальной логики L понимается сложность следующей массовой задачи: по данной формуле A определить, выполнима ли формула A на некоторой шкале логики L. Эта задача является двойственной к задачи выводимости в логике, т.к. формула A выводима в L тогда и только тогда, когда формула \lnot A невыполнима на L-шкале. Сложностной класс PSPACE содержит все массовые задачи, которые можно решить на машине Тьюринга, которая использует не больше полинома от длины входа ячеек ленты в процессе выполнения.
Мы будем рассматривать слаботранзитивные логики, т.е. логики содержащие wK4 = K + \Box p \land p \to \Box \Box p.
Общезначимость этой логики соответствует тому, что рефлексивное замыкание отношения - транзитивно.
Добавление универсальной модальности увеличивает выразительную силу языка. Добавление универсальной модальности рассматривалось в 90-е годы в работах Горанко и Пасси, а в работе Шехтмана было доказано, что в языке с универсальной модальностью можно выразить связность.
Мы покажем, что если проблема выполнимости для логики с универсальной модальностью некоторого класса слаботранзитивных шкал содержится в сложностном классе PSPACE, то добавление к этой логике аксиомы связности не выведет из класса PSPACE.
➰ ВК
Яндекс Карты
МФТИ, радиотехнический корпус: как доехать на автомобиле, общественным транспортом или пешком – Яндекс Карты
МФТИ, радиотехнический корпус: варианты маршрутов с указанием расстояния и времени в пути. Яндекс Карты покажут, как добраться до нужного места на разных видах транспорта или пешком.
👍1