#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), only Kontur Talk (www.mathnet.ru/eng/conf876)

17.03.2025 семинара не будет

24.03.2025 В.Л. Селиванов, И.В. Смирнов (СПбГУ): Ординальные инварианты гомоморфных предпорядков к-размеченных лесов

В докладе обсуждается комбинаторная сложность хороших частичных порядков (ХЧП). Название является калькой английского термина WPO (Well Partial Order)-theory (часто встречается также название WQO-theory). К сожалению, в русскоязычной литературе нет общепринятого наименования этой теории, в которой изучаются частичные порядки, не имеющие бесконечно убывающих цепей и бесконечных антицепей; такие порядки и называются хорошими. Теория ХЧП имеет богатую историю и приложения к различным разделам математики и информатики.

К числу инструментов теории ХЧП относятся так называемые ординальные инварианты, т.е. ординалы, измеряющие те или иные аспекты комбинаторной сложности ХЧП. Вычисление ординальных инвариантов конкретных ХЧП (высоты, ширины и максимального ординала) часто оказывается нетривиальной задачей, которая к настоящему времени решена лишь для небольшого числа важных ХЧП.

В данной работе вычислены (в терминах ординалов Веблена) ординальные инварианты для конкретных указанных в заглавии ХЧП, введенных П. Хертлингом и нашедших приложения в дескриптивной теории множеств и теории автоматов на бесконечных словах.

➰ ВК