Алгебраические и логические методы в компьютерных науках

Последнее изменение: 11/01/2017 12:32:20

Обязательный курс для 1-го курса магистратуры-КН, ПИ, ФИИТ. Рекомендуется как специальный курс для 1-го курса магистратуры-МТ и для студентов старших курсов бакалавриата. В осеннем семестре 2016/17 учебного года читается по понедельникам с 10:40 в ауд. 632.

Зачет по курсу состоится 27.01.17 в ауд.513, начало в 9:00.

Конспект лекций - обновлено 02.10.16. Замечания по конспекту лекций (опечатки, непонятные места и т.п.) приветствуются!

Литература для дополнительного чтения

  • Jean-Éric Pin. Varieties of formal languages. North Oxford, London & Plenum, New-York, 1986.
  • Howard Straubing. Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA, 1994.

Краткое содержание курса

  • Алгебраическая теория формальных языков
    • Теоремы Щютценберже и Саймона
    • Теория Эйленберга и ее современные обобщения
  • Логическая теория формальных языков
    • Монадическая логика второго порядка. Результаты Бюхи
    • Теорема Макнотона
    • Соответствие между логическими и алгебраическими иерархиями
  • Линейная темпоральная логика
  • Верификация программных систем

Вопросы к зачету по итогам осеннего семестра

  1. Отношения Грина и их основные свойства. Лемма Грина
  2. Теорема Миллера-Клиффорда. Регулярные D-классы
  3. D-строение моноида преобразований
  4. Алгоритм вычисления регулярных D-классов в полугруппах преобразований
  5. Моноид переходов автомата. Алгоритм вычисления моноида переходов. Языки, распознаваемые моноидами
  6. Конгруэнции полугрупп. Факторполугруппа. Синтаксическая конгруэнция языка. Синтаксический моноид
  7. Синтаксический моноид как моноид переходов минимального автомата
  8. Кусочно тестируемые языки. Отношение равноподсловности. Формулировка теоремы Саймона
  9. Первые два комбинаторных предложения из доказательства теоремы Саймона.
  10. Доказательство достаточности условия теоремы Саймона (кусочно тестируемый язык распознается J-тривиальным моноидом)
  11. Основное комбинаторное предложение из доказательства теоремы Саймона
  12. Доказательство необходимости теоремы Саймона (язык, распознаваемый J-тривиальным моноидом, кусочно тестируем).
  13. Произведение Щютценберже. Доказательство достаточности условия теоремы Щютценберже (беззвездный язык распознается H-тривиальным моноидом)
  14. Доказательство необходимости теоремы Щютценберже (язык, распознаваемый H-тривиальным моноидом, беззвездный).

Смотрите также: