Search
Пятница 21 сентября, 17-00, ауд. 203
Пятница, 21 сентября, ауд. 203. Начало в 17:00.
Докладчик: А. Э. Фрид (Институт математики им. С. Л. Соболева СО РАН).
Тема: Линейная арифметическая сложность бесконечных слов.
Abstract
Арифметической замыканием бесконечного слова называется множество слов, встречающихся в нем по арифметическим прогрессиям. В этих терминах теорема Ван дер Вардена гласит, что в арифметическом замыкании любого слова есть слово
для всех 
и для некоторого
символа a. Арифметическая сложность слова, введенная С. В. Августиновичем, Д. Г. Фон-Дер-Флаассом и автором в 2000 году, определяется как количество слов длины n в арифметическом замыкании слова.
Слово называется равномерно рекуррентным, если каждое его подслово встречается в нем бесконечное число раз с ограниченным расстоянием между соседними вхождениями. Доклад будет посвящен полученной автором характеризации равномерно рекуррентных слов, арифметическая сложность которых растет всего лишь линейно.