Научно-исследовательский семинар
по математической логике
руководители:
академик РАН   С.И.Адян
чл.-корр. РАН   Л.Д.Беклемишев
академик РАН   А.Л.Семёнов


YouTube-канал семинара

    ОСЕНЬ 2018
  1. 2018.11.21: Секвенциальные исчисления с нефундированными выводами для логик Гжегорчика
    Докладчик: Саватеев Юрий Вячеславович
    Видеозапись доклада: YouTube
    Аннотация. В докладе будут предложены секвенциальные исчисления с нефундированными выводами для логики Гжегорчика Grz и слабой логики Гжегорчика wGrz. Для этих исчислений строится оператор удаления сечения как неподвижная точка нерастягивающего отображения в ультраметрическом пространстве.
  2. 2018.11.07: Сложность конечных автоматов в терминах количества состояний и ее поведение при различных операциях
    Докладчик: Раскин Михаил Александрович
    Видеозапись доклада: YouTube
    Аннотация. Детерминированные и недетерминированные конечные автоматы распознают одно и то же семейство языков. Хорошо известно, что детерминизация может приводить к экспоненциальному росту числа состояний. (Естественно напрашиваются аналогии с проблемой перебора.) Можно выделить некоторые промежуточные классы конечных автоматов, например, однозначные конечные автоматы, а также различные другие модификации конечных автоматов. Операции над языками при разных представлениях будут по-разному влиять на количество состояний.

    В докладе будет дан обзор результатов о сложности в терминах количества состояний для разных видов автоматов и приведены некоторые новые результаты.

  3. 2018.10.24: Computability aspects in multidimensional symbolic dynamics (на английском языке)
    (Алгоритмические свойства многомерных замощений)
    Докладчик: Pierre Guillon (Пьер Гийон) (CNRS & Centre interdisciplinaire franco-russe Poncelet)
    Видеозапись доклада: YouTube
    Abstract. A 1D subshift of finite type (SFT) is a set of biinfinite words over a given finite alphabet, defined by prohibiting a finite set of finite patterns. 1D SFT can be studied thanks to linear algebra, graph theory, automata theory. The 2D version of this object, however, corresponds to tilings by Wang tiles, and relies strongly on computability theory.

    We will survey some uncomputability and characterization results in this setting: domino problem, language, entropies, traces, periods, quasiperiods, Kolmogorov complexity, Turing degrees. If time permits, we will conclude with open questions, especially in the larger setting of Cayley graphs.

  4. 2018.10.10: Экспандеры и связь коммуникационной и вопросной сложности
    Докладчики: Козачинский Александр Николаевич и Верещагин Николай Константинович
    Видеозапись доклада: YouTube
    Аннотация. Доклад посвящён техникам получения нижних оценок для трёх видов сложности вычислений: схемной (рассматривавшейся начиная с 1950-х годов), коммуникационной и вопросной. Будет описана техника сведения одних оценок к другим и приведены результаты автора, относящиеся к ограниченности этой техники.
  5. Избранные доклады прошлых лет
  6. 2018.04.04: Замощения Аммана
    Докладчик: Верещагин Николай Константинович
    Аннотация. Доклад по статье Верещагина, Дюрана и Шеня: On the structure of Ammann A2 tilings.
  7. 2017.11.22: Конструктивные семантики логических языков, основанные на обобщённой вычислимости
    Докладчик: Коновалов Александр Юрьевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: доц. В.Е.Плиско.
  8. 2017.11.15: Interpolation, Amalgamation and Combination (на английском языке)
    Докладчик: Silvio Ghilardi (Сильвио Гиларди)
  9. 2017.05.31: О некоторых вопросах алгоритмической статистики
    Докладчик: Милованов Алексей Сергеевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. Н.К.Верещагин.
  10. 2017.04.19: Ломоносовские чтения 2017
    Доклады:
    1. Нестохастические объекты в алгоритмической статистике.
      Докладчики: Верещагин Николай Константинович (проф.), Милованов Алексей Сергеевич (асп.).
    2. О спектрах консервативности для арифметических теорий.
      Докладчик: Беклемишев Лев Дмитриевич (проф., чл.-корр. РАН).
    3. О моделировании знания в социальных сетях.
      Докладчик: Крупский Владимир Николаевич (доц.).
    4. Кратчайшая перестройка данных графов, одного в другой:
      линейный алгоритм или сведение к целочисленному линейному программированию.
      Докладчик: Любецкий Василий Александрович (проф.).
    5. О конструктивной теории перечислимых видов.
      Докладчик: Плиско Валерий Егорович (доц.).
    6. О понятии исчисления.
      Докладчики: Семёнов Алексей Львович (проф., академик РАН), Успенский Владимир Андреевич (проф.).
    7. О пространствах выразимости.
      Докладчик: Семёнов Алексей Львович (проф., академик РАН).
    8. Структура пространств выразимости для следования на целых числах.
      Докладчик: Семёнов Алексей Львович (проф., академик РАН), Сопрунов Сергей Федорович (с.н.с. ВЦ РАН).
    9. О полноте некоторых предикатных модальных логик.
      Докладчик: Шехтман Валентин Борисович (проф.).
  11. 2017.04.12: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2017»
    Доклады:
    1. Власов Илья Игоревич
      (Казанский (Приволжский) государственный университет)
      Умеренно низкие и супернизкие множества (аннотация)
    2. Запрягаев Александр Александрович
      (МГУ, 5-й курс, научный руководитель: чл.-корр. РАН Л. Д. Беклемишев)
      Интерпретации арифметики Пресбургера в себя
  12. 2017.02.15: Об элиминации итеративных операторов в некоторых теориях первого порядка
    Докладчик: Золотов Александр Сергеевич (Казанский федеральный университет)
    Аннотация. Доклад посвящен исследованию алгоритмических свойств разрешимых арифметических теорий первого порядка, обогащенных итеративными операторами: оператором транзитивного замыкания и оператором фиксированной точки. В некоторых случаях удается эффективно элиминировать данные операторы, что позволяет сделать выводы о разрешимости обогащений. В других случаях обогащение оказывается неразрешимым. Также для фрагмента теории целых чисел с функцией следования и одноместным оператором наименьшей фиксированной точки, применяемым только к экзистенциальным формулам, установлена полнота проблемы разрешимости в классе гиперэкспоненциальной временной сложности.
  13. 2016.11.02: Сравнение игровыми методами понятий префиксной и обычной колмогоровской сложности
    Докладчик: Андреев Михаил Александрович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. Н.К.Верещагин.
  14. 2016.04.27: Ломоносовские чтения 2016
    Доклады:
    1. Бисимуляционные игры и неклассические логики
      Докладчик: Шехтман Валентин Борисович (профессор, д.ф.-м.н.)
    2. Модальные логики операций на шкалах Крипке
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
  15. 2016.04.13: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2016»
    Доклады:
    1. Вахрушева Полина Викторовна
      (МГУ, аспирант, научный руководитель: проф. В. Б. Шехтман)
      Свойства некоторых временных гибридных логик
    2. Запрягаев Александр Александрович
      (МГУ, 4-й курс, научный руководитель: чл.-корр. РАН Л. Д. Беклемишев)
      Интерпретации арифметики Пресбургера в себя
    3. Маслов Николай Александрович
      (научный руководитель: проф. В. Б. Шехтман)
      Бисимуляционная игра Эренфойхта для предикатных моделей Крипке с постоянной областью
    4. Милованов Алексей Сергеевич
      (МГУ, аспирант, научный руководитель: проф. Н. К. Верещагин)
      Некоторые свойства антистохастических слов
  16. 2015.04.15: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2015»
    Доклады:
    1. Осипов Илья Игоревич
      Теоремы о характеризации для бимодальной логики
  17. 2014.05.21: Некоторые результаты об автоматах на сверхсловах, полученные с помощью прямого и полупрямого произведения
    Докладчик: Раскин Михаил Александрович
  18. 2014.04.16: Ломоносовские чтения 2014
    Доклады:
    1. Коммуникационная сложность приближённого нахождения колмогоровской сложности
      Докладчик: Верещагин Николай Константинович (профессор, д.ф.-м.н.)
    2. Локальный аналог теоремы Гольдблатта-Томасона в модальной логике
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
  19. 2013.09.18: Отношение совместимости в двух вариантах исчисления Ламбека
    Докладчик: Сорокин Алексей Андреевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. М.Р.Пентус.
  20. 2013.05.22: Применения графов в теории колмогоровской сложности
    Докладчик: Мусатов Даниил Владимирович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. Н.К.Верещагин.
  21. 2013.04.24: Ломоносовские чтения 2013
    Доклады:
    1. Вычисление небольшого списка, содержащего короткое описание данного объекта
      Докладчик: Верещагин Николай Константинович (профессор, д.ф.-м.н.)
    2. Клетчатые произведения модальных логик
      Докладчики: Шехтман Валентин Борисович (профессор, д.ф.-м.н.), Шапировский Илья Борисович (с.н.с. ИППИ РАН, к.ф.-м.н.)
  22. 2013.04.10: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2013»
    Доклады:
    1. Андреев Михаил Александрович
      (МГУ, 5-й курс, научные руководители: проф. Н. К. Верещагин, А. Шень)
      Различные варианты α-нулевых множеств и их сравнение
    2. Колесниченко Игнатий Игоревич
      (МГУ, аспирант, научные руководители: асс. М. А. Бабенко, проф. Н. К. Верещагин)
      О минимальных окончаниях подслов
  23. 2012.12.05: Конструкция Хрушовского и гипотезы Шануэля и Андрэ
    Докладчик: Зильбер Борис Иосифович
    Аннотация. Конструкция Хрушовского является (eдинственным) источником контрпримеров к гипотезе докладчика о том, что все теории, категоричные в несчётных мощностях, сводятся к алгебраической геометрии. Тем не менее, более глубокий анализ показывает, что эти контрпримеры не очень далеки от алгебраической геометрии и связаны с классическими трансцендентными функциями. При этом один из ключевых элементов конструкции Хрушовского соответствует условию, сформулированному в частном случае в известной гипотезе Шануэля, и её глубокому обобщению — гипотезе Ива Андрэ.
  24. 2012.10.31:
    1) Разрешимость теории иерархий согласованных со сложением функций
    Докладчик: Снятков Алексей Сергеевич (Тверской государственный университет)
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: д.ф.-м.н., доц. С.М.Дудаков.

    2) Эффективные алгоритмы для некоторых задач обработки слов
    Докладчик: Стариковская Татьяна Андреевна
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: к.ф.-м.н. М.А.Бабенко.
  25. 2012.04.11: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2012»
    Доклады:
    1. Андреев Михаил Александрович (МГУ, 4-й курс)
      Эффективная хаусдорфова размерность и случайность по классам мер
    2. Пахомов Федор Николаевич (МГУ, 5-й курс)
      PSPACE-полнота замкнутого фрагмента полимодальной логики доказуемости
    3. Савин Арсений Анатольевич (МГУ, 4-й курс)
      Тотально вычислимая колмогоровская сложность
  26. 2012.03.28:
    1) О пропозициональных исчислениях, представляющих понятие доказуемости
    Докладчик: Дашков Евгений Владимирович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. Л.Д.Беклемишев.
    2) Категориальные грамматики, основанные на вариантах исчисления Ламбека
    Докладчик: Кузнецов Степан Львович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации. Научный руководитель: проф. М.Р.Пентус.
  27. 2011.12.14: Добавление случайных аксиом и теорема Гёделя
    Докладчик: Шень Александр
    Аннотация. Теорема Гёделя в форме Чейтина показывает, что утверждения вида «колмогоровская сложность x больше c», где x — конкретное слово, а c — конкретное число, недоказуемы для всех достаточно больших с. С другой стороны, мы практически уверены, что бросание честной монеты позволяет получить пары x, c, для которых такие утверждения истинны (считая противное невероятным). Что будет, если добавлять такие утверждения в качестве аксиом? Можно ли таким образом преодолеть ограничения, накладываемые теоремой Гёделя? В докладе этот вопрос будет уточнён и показано (в некотором точном смысле), что надежды получить новые интересные утверждения таким способом нет, а вот сокращение доказательств тут возможно."
  28. 2011.11.16: Ломоносовские чтения 2011
    Доклады:
    1. Проблема глобальной выполнимости в полимодальных градуированных логиках
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
    2. Квадраты модальных логик с дополнительными связками
      Докладчик: Шехтман Валентин Борисович (профессор, д.ф.-м.н.)
    3. Интерполяционные свойства логик доказуемости и нормализация термов рефлексивной комбинаторной логики
      Докладчик: Шамканов Данияр Салкарбекович (аспирант)
      Аннотация. Краткое изложение результатов представляемой к защите диссертации.
      Научные руководители: проф. Л.Д.Беклемишев, доц. В.Н.Крупский.
  29. 2010.09.22: О некоторых суперинтуиционистских логиках, связанных с логикой задач Колмогорова – Медведева
    Докладчик: Шатров Тимофей Анатольевич
    Научный руководитель: проф. В.Б.Шехтман

Собрал информацию: уч. секретарь кафедры Е.Е.Золин
HTML 4.01   CSS 3