Semilattice of roots from formal languages of a special kind
Svetlana Korabelshchikova · International journal of open information technologies · 2020
В данной статье представлен результат изучения структуры множества корней из языков специального вида, а именно содержащих всевозможные слова длины от t 1 до t 2 (t 1 £ t 2 ). Изучен общий случай извлечения корней n-й степени из данного языка, приведены алгоритмы нахождения всех корней из языка, первообразных корней, а также результаты работы программ, реализующих предложенные алгоритмы. Рассматриваемая задача сводится к задаче о рюкзаке и решается методом программной реализации предложенных алгоритмов. На множестве корней из языка задается отношение порядка, определяются минимальные и максимальные элементы. В работе показано, что множество корней из языков специального вида либо пусто, либо образует верхнюю полурешетку, минимальными элементами которой являются первообразные корни, а максимальным – тривиальный корень из данного языка. Приведены наглядные простые примеры, которые иллюстрируют неоднозначность операции извлечения корня из языка, связь между множествами корней из двух языков с равномощными множествами индексов, свойства первообразных корней, строение полурешетки корней. Полученные результаты могут применяться для компактного описания множеств корней и аналогичных им множеств, а также для их количественных оценок.