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

Последнее изменение: 26/12/2016 23:41:59

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

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

  • 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-тривиальным моноидом)
  15. Многообразия конечных моноидов и многообразия регулярных языков. Теорема Эйленберга

Зачет состоится в понедельник 22.12 в ауд. 611, начало в 11:00

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