
Arctic Environmental Research
A peer-reviewed open-access journal
e-ISSN 2658-7173 DOI:10.3897/issn2541-8416
![]()
Учредитель: Северный (Арктический) федеральный университет им. М.В. Ломоносова Адрес редакции: 163002, Архангельская обл., г. Архангельск, наб. Северной Двины, д. 17, каб. 1410а
Тел: (818-2) 21-61-00(15-33) e-mail: l.zhgileva@narfu.ru Сайт: http://aer.narfu.ru/ 16+ О журнале |
Рубрика: Физика, Математика, Информатика УДК519.713Сведения об авторахКорабельщикова Светлана Юрьевна, кандидат физико-математических наук, доцент кафедры математического анализа, алгебры и геометрии института математики, информационных и космических технологий Северного (Арктического) федерального университета имени М.В. Ломоносова. Автор 22 научных публикаций, в т. ч. одной монографииМельников Борис Феликсович, доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики и информатики Тольяттинского филиала Самарского государственного университета. Автор около 200 научных публикаций, в т. ч. 6 монографий
АннотацияВ данной работе рассматривается связь максимальных префиксных кодов с теорией формальных языков и алфавитным кодированием. В терминах максимальных префиксных кодов формулируются условия коммутирования в глобальном надмоноиде свободного моноида, критерий эквивалентности пары конечных языков и ряд других результатов, связанных с бесконечными итерациями языков. Многие из этих результатов связаны с алгоритмическими проблемами для мономиальных алгебр (т. е. ассоциативных алгебр, заданных с помощью так называемых языков обструкций).В алфавитном кодировании преимущественно используются префиксные коды, т. к. свойство префикса гарантирует однозначную декодируемость. Максимальные префиксные коды обладают рядом дополнительных свойств: в неравенстве Макмиллана для них выполняется равенство; все вершины кодового дерева являются насыщенными.
Мы использовали соответствие между максимальными префиксными кодами и кодовыми деревьями, благодаря чему нами произведен подсчет числа максимальных префиксных кодов заданной мощности r в q-буквенном алфавите. В работе получена общая формула, приведены примеры ее применения.
Максимальных префиксных кодов мощности r над q-буквенным алфавитом не существует, если остаток от деления r на q-1 не равен 1.
Частное k от деления r на q-1 можно интерпретировать как максимальное число ярусов в кодовом дереве, а также как количество пучков из q ребер, составляющих дерево. Набор (n1, n2, n3, … , ns) представляет собой распределение этих пучков по ярусам кодового дерева.
В заключение приведен ряд нерешенных задач, сформулированы гипотезы необходимых условий коммутирования, требующие проверки.
Ключевые словаконтекстно-свободный язык, префиксный код, кодовое дерево, максимальный префиксный код.Список литературы
|