|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О минимальной склейке регулярных языков с линейной функцией ростадипломная работа (Магистр)
- Научный руководитель: Дергач П.С.
- Автор: Раджабов Жахонгир Ихтиёр угли
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: В работе Ж. Раджабова решается следующая задача. Рассматривается класс регулярных языков с линейной функцией роста в двухэлементном алфавите {a,b}. Сложностью такого языка называем Глубиной этого представления называем число s. На такие языки действует функция f побуквенного алфавитного кодирования. Сложностью функции кодирования называем максимальную длину ее элементарных кодов f(a),f(b). Задача состоит в том, чтобы оценить сверху и снизу самое большое значение длины образа минимальной склейки, то есть пары различных слов языка с совпадающим образом. При этом рассматриваются только такие языки нашего вида и такие функции кодирования, которые имеют сложность не выше k и у которых есть хоть одна склейка. Известно, что в двухэлементном алфавите есть общий вид f(a)=(alpha)^m, f(b)=(alpha)^n схем кодирования, имеющих хоть одну склейку. Поэтому при поиске минимальной длины образа склейки достаточно ограничиться рассмотрением схем вида f(a)=0^n,f(b)=0^m. Жахонгир смог найти соответствующую нижнюю оценку для класса языков глубины 2 и соответствующую верхнюю оценку для класса языков произвольной глубины. Для класса языков глубины 2 оценки совпали по порядку (отличие в 2 раза). Нижняя оценка получена конструктивно, верхняя – изящным рассуждением о псевдосклейках (лемма 1).
- Добавил в систему: Дергач Пётр Сергеевич