Выполнение научно-исследовательской работы "Периодичность, избегаемость и сложность слов и формальных языков".

Результаты работы.
1. Изучено современное состояние научных исследований по теме работы и в смежных областях теории формальных языков, теории автоматов, комбинаторики слов и теории сложности, собрана необходимая информация.
2. Получены консультации по следующим вопросам научных исследований: «Комбинаторная сложность бесконечных слов», «Слова Штурма и преобразование Бэрроуза-Уилера», «Обобщения теоремы о критическом разбиении, в том числе для многомерных и частичных слов», «Проблема Конвея о максимальном языке, коммутирующем с данным».
3. Освоены методики научных исследований по тематике работы: «Применение конечных автоматов, трансдьюсеров и машин Тьюринга для исследования комбинаторных вопросов в теории формальных языков», «Получение нижних оценок комбинаторной сложности языков при помощи морфизмов», «Применение теоремы о критическом разбиении и ее обобщений к исследованию периодичности».
4. Проведены компьютерные эксперименты по оценке комбинаторной сложности формальных языков, периодических свойств частичных слов и влиянию преобразования Бэрроуза-Уилера на некоторые известные в комбинаторике последовательности.
5. Подготовлены и опубликованы в серии «TUCS technical reports» (Технические доклады Центра компьютерных наук Турку) следующие статьи: «Polynomial languages with finite antidictionaries» (Полиномиальные языки с конечными антисловарями), «On intermediate factorial languages» (О промежуточных факториальных языках), «Rational approximations of polynomial factorial languages» (Рациональные приближения полиномиальных факториальных языков), «Languages with finite antidictionaries: growth rate and graph properties».
6. Результаты исследований легли в основу научного доклада на международную конференцию CSR (Санкт-Петербург, 2006). Сделано три доклада на семинаре по теории автоматов и комбинаторике слов университета Турку (руководитель – академик А.Саломаа). Темы докладов: «Complexity of languages» (Сложность языков), «Web-like automata: further applications to combinatorial complexity» (Паутинные автоматы: дальнейшие применения к комбинаторной сложности), «Periodic partial words» (Периодические частичные слова).
7. Изучены методики преподавания компьютерных наук, в частности, таких дисциплин, как «Конечные автоматы», «Теория формальных языков», «Комбинаторика слов», «Комбинаторные структуры», «Теория графов»;
8. Подобраны учебно-методические материалы по дисциплинам, перечисленным в п.7, для использования в Уральском государственном университете им. А.М. Горького.
Областью применения является комбинаторика слов, теория формальных языков, теория конечных автоматов и смежные разделы дискретной математики.