Аннотация:
В докладе будут кратко и неформально обсуждены сводимость Вэджа (играющая заметную роль в дескриптивной теории множеств) и ее конструктивные варианты (играющие заметную роль в теории автоматов на бесконечных словах и деревьях). Конструктивные варианты сводимости Вэджа появились в контексте иерархии Вагнера регулярных языков бесконечных слов в виде замечательной теоремы Бюхи-Ландвебера.
Это обширное направление тесно связано с играми Гейла-Стюарта, теорией стройных частичных порядков, и теорией операций над множествами (сыгравшей основную роль в возникновении дескриптивной теории множеств более века назад).
Обратная связь: