Спецкурс "Теория полугрупп и ее приложения в компьютерных науках"

Последнее изменение: 01/05/2023 20:21:34

Спецкурс призван дать быстрое, но вполне строгое введение в основные идеи современной теории полугрупп и обсудить некоторые важные приложения этой теории к формальным языкам и конечным автоматам.

Спецкурс читается по пятницам 4-й парой в ауд. 608.

План курса

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

Тексты лекций

Лекция 1: Постановка задачи, отношения Грина

Лекция 2: Отношения Грина в моноиде всех преобразований, лемма Грина

Лекция 3: Отношения Грина и идемпотенты

Лекция 4: Алгоритм вычисления регулярных D-классов

Лекция 5: Моноид переходов. Алгоритм вычисления моноида переходов

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