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

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

Вы можете купить электронную версию издания «Максимальные префиксные коды и подклассы класса контекстно-свободных языков». После оплаты (для архивов) оно будет доступно в Личном Кабинете в разделе «Электронные издания». В случае оформления подписки, издание будет доступно по мере поступления от издателя. Формат PDF/HTML. Стоимость — от 90.00 руб.