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

Проведение научных исследований молодыми учеными. Комбинаторные характеризации формальных языков.

Стадии проекта
Предложение принято
Конкурс завершен
Выполнение этапа проекта
Продолжительность работ
2006, 7 мес.
Бюджетные средства
0,4 млн
Внебюджетные средства
0 млн

Информация отсутствует

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

1
06.03.2006 - 31.05.2006
построение усовершенствованного алгоритма вычисления сложности языков с конечными антисловарями. Разработка программы, реализующей алгоритм. Получение уточненных экспериментальных оценок сложности для ряда важных языков. Разработка программ, реализующих алгоритмы поиска автоморфизмов и делителей ориентированных графов. Применение данных программ для сравнительного анализа автоматов, распознающих исследуемые языки. Теоретический анализ языков малой сложности. Выбор математической модели источника информации для тестирования схем сжатия. Разработка и программная реализация алгоритма проверки специальности периодического частичного слова. Составление промежуточного отчета.
Развернуть
2
01.06.2006 - 02.10.2006
Результаты работы.
1. Доказано, что все полиномиальные классы сложности возможны для языков с конечными и конечными симметричными антисловарями; получены нижние и верхние оценки сложности ряда языков;
2. Доказано совпадение индексов роста произвольного языка L и его продолжаемого подмножества L’; показано, что между L и L’ возможен суперполиномиальный скачок сложности;
3. Построен усовершенствованный алгоритм вычисления сложности языков с конечными антисловарями; разработана программа, реализующая этот алгоритм; получены уточненные экспериментальные оценки сложности для ряда важных языков;
4. Проведен ряд компьютерных экспериментов для экспоненциальных языков с конечными антисловарями; произведены вычисления подграфов в этих автоматах, определяющие индекс роста распознаваемого языка (С-графы); получен список С-графов не более, чем с четырьмя вершинами для двухбуквенного алфавита и не более, чем с тремя вершинами для трехбуквенного алфавита; аналитически доказано, что списки являются исчерпывающими;
5. Изучены свойства синхронизируемых автоматов, в которых одна из букв является 2-сжимающей; построены две бесконечные серии примеров, дающие нижнюю оценку максимума длины кратчайшего синхронизирующего слова для двух классов таких автоматов;
6. Исследована «бережная синхронизируемость» частичных автоматов, получена нижняя оценка длины кратчайшего слова, бережно синхронизирующего частичные автоматы;
7. Положительно решен вопрос об алгоритмической распознаваемости сжимающих слов; Показано, что любое 2-синхронизирующее слово, прочитанное с конца к началу, снова является 2-синхронизирующим;
8. Найден критерий специальности частичного слова; на основе данного критерия разработан полиномиальный алгоритм с конечной памятью проверки специальности периодического частичного слова; создана программа, реализующая этот алгоритм; получены экспериментальные результаты о частоте встречаемости специальных частичных слов и связанных с этим закономерностях;
9. Построен генератор марковских источников информации с автоматическим вычислением энтропии; разработан и реализован ряд адаптивных и неадаптивных вариантов алгоритмов сжатия результата на основе бинарного преобразования Бэрроуза-Уилера; изучено поведение построенных схем сжатия на произвольных марковских последовательностях.

Область применения.
Областью применения является комбинаторика слов, теория формальных языков, теория конечных автоматов и смежные разделы дискретной математики.

Прогнозные предположения о развитии объекта исследования.
Предполагается, что данная тематика будет вызывать растущий интерес специалистов в ближайшие годы. Ожидается увеличение числа молодых исследователей в данной области в Уральском госуниверситете.
Развернуть

Программа

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

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

1.9 Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования
Продолжительность работ
2012 - 2013, 15 мес.
Бюджетные средства
1,32 млн
профинансировано
Продолжительность работ
2005, 1 мес.
Бюджетные средства
0,36 млн
Организация
ИСП РАН
профинансировано
Продолжительность работ
2012, 4 мес.
Бюджетные средства
2,6 млн
профинансировано
Продолжительность работ
2012 - 2013, 13 мес.
Бюджетные средства
1,18 млн
Организация
ПОМИ РАН
профинансировано
Тема
Создание катализаторов на принципах функционирования ферментов. Комбинаторная химия в конструировании моделей ферментов
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
6 млн
Количество заявок
4
Тема
Разработка нейтронографических методов характеризации наноструктур в функциональных материалах.
Продолжительность работ
2005 - 2006, 23 мес.
Бюджетные средства
6 млн
Количество заявок
4
Тема
Разработка диагностико-технологического кластера для изготовления и характеризации МЭМС и НЭМС.
Продолжительность работ
2009 - 2011, 24 мес.
Бюджетные средства
150 млн
Количество заявок
1
Тема
Комбинаторные подходы к созданию новых ингибиторов ключевых протеиназ развития нейродегенеративных и инфекционных заболеваний.
Продолжительность работ
2008 - 2009, 17 мес.
Бюджетные средства
7,8 млн
Количество заявок
2
Тема
Изучение механизмов прогрессии опухолей и создание новых методов подавления роста опухолей и метастазов, в том числе, с помощью комбинаторной терапии.
Продолжительность работ
2008, 3 мес.
Бюджетные средства
1,2 млн
Количество заявок
1