Максимальные префиксные коды и подклассы класса контекстно-свободных языков

В данной работе рассматривается связь максимальных префиксных кодов с теорией формальных языков и алфавитным кодированием. В терминах максимальных префиксных кодов формулируются условия коммутирования в глобальном надмоноиде свободного моноида, критерий эквивалентности пары конечных языков и ряд других результатов, связанных с бесконечными итерациями языков. Многие из этих результатов связаны с алгоритмическими проблемами для мономиальных алгебр (т. е. ассоциативных алгебр, заданных с помощью так называемых языков обструкций). В алфавитном кодировании преимущественно используются префиксные коды, т. к. свойство префикса гарантирует однозначную декодируемость. Максимальные префиксные коды обладают рядом дополнительных свойств: в неравенстве Макмиллана для них выполняется равенство; все вершины кодового дерева являются насыщенными. Мы использовали соответствие между максимальными префиксными кодами и кодовыми деревьями, благодаря чему нами произведен подсчет числа максимальных префиксных кодов заданной мощности r в q-буквенном алфавите. В работе получена общая формула, приведены примеры ее применения. Максимальных префиксных кодов мощности r над q-буквенным алфавитом не существует, если остаток от деления r на q-1 не равен 1. Частное k от деления r на q-1 можно интерпретировать как максимальное число ярусов в кодовом дереве, а также как количество пучков из q ребер, составляющих дерево. Набор (n 1, n 2, n 3, …, n s) представляет собой распределение этих пучков по ярусам кодового дерева. В заключение приведен ряд нерешенных задач, сформулированы гипотезы необходимых условий коммутирования, требующие проверки.

• Мельников Б.Ф.
• Корабельщикова С.Ю. Юрьевна
• Феликсович

• Естественные науки
• Технические науки. Промышленность
• Физико-математические науки