Регистрация / Вход
Прислать материал

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

Стадии проекта
Предложение принято
Конкурс завершен
Выполнение этапа проекта

Проведение стажировок в зарубежных научно-образовательных центрах

Соисполнители

Организация
Университет Турку

Этапы проекта

1
05.09.2005 - 09.12.2005
Результаты работы.
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, для использования в Уральском государственном университете им. А.М. Горького.
Областью применения является комбинаторика слов, теория формальных языков, теория конечных автоматов и смежные разделы дискретной математики.
Развернуть

Программа

Программа "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы

Программное мероприятие

1.11 Развитие системы стажировок молодых ученых и преподавателей в крупных научно-образовательных центрах (включая зарубежные) и участие в конференциях, симпозиумах, семинарах, школах (в том числе за рубежом)
Продолжительность работ
2014 - 2018, 57 мес.
Бюджетные средства
97 млн
Организация
ПОМИ РАН
профинансировано
Продолжительность работ
2005, 3 мес.
Бюджетные средства
0,17 млн
Организация
БИН РАН
профинансировано
Продолжительность работ
2005, 3 мес.
Бюджетные средства
0,09 млн
Организация
БИН РАН
профинансировано
Тема
Выполнение научно-исследовательских, опытно-конструкторских и технологических работ молодыми учеными и преподавателями во время проведения стажировок в зарубежных научно-образовательных центрах.
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
26,4 млн
Количество заявок
66
Тема
Выполнение научно-исследовательских, опытно-конструкторских и технологических работ молодыми учеными и преподавателями во время проведения стажировок в зарубежных научно-образовательных центрах.
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
17,6 млн
Количество заявок
42
Тема
Выполнение научно-исследовательских работ молодыми учеными и преподавателями во время проведения стажировок в зарубежных научно-образовательных центрах (в том числе с участием в конференциях, симпозиумах, семинарах, школах).
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
46 млн
Количество заявок
153
Тема
Выполнение научно-исследовательских, опытно-конструкторских и технологических работ молодыми учеными и преподавателями во время проведения стажировок в российских научно-образовательных центрах.
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
7,2 млн
Количество заявок
64
Тема
Выполнение научно-исследовательских, опытно-конструкторских и технологических работ молодыми учеными и преподавателями во время проведения стажировок в российских научно-образовательных центрах.
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
28,8 млн
Количество заявок
174