Об алгоритмической сложности задач оптимального алфавитного кодирования для контекстно-свободных языков

Рассмотрена комбинаторно-логическая модель алфавитного кодирования, учитывающая структурные свойства языка сообщений. В качестве языков сообщений рассмотрены ближайшие известные расширения регулярных языков – контекстно-свободные (КС-языки) и детерминированные КС-языки (ДКС-языки). Для классов моделей алфавитного кодирования КС- и ДКС-языков доказана алгоритмическая неразрешимость одной из основных проблем кодирования – проблемы оптимального кодирования (в смысле стоимости).
Исследована принципиальная возможность решения проблемы оптимального кодирования при двух видах ограничений на сложность декодирования: при декодировании с конечной задержкой и конечно-автоматном декодировании. Показано, что рассматриваемые ограничения на декодирование для нерегулярных моделей языков не совпадают и не включены одно в другое.