Том 8, серия 1, номер 3, 2001 г., Стр. 26-45
УДК 519.713
Л. П. Жильцова
О нижней оценке стоимости кодирования и асимптотически оптимальном кодировании стохастических контекстно-свободных языков
Аннотация:
Рассматривается язык, порожденный стохастической контекстно-свободной грамматикой с однозначным выводом, для которой матрица первых моментов неразложима, непериодична и ее перронов корень строго меньше 1. Для такого языка получена неулучшаемая нижняя оценка стоимости двоичного кодирования. Построен также алгоритм асимптотически оптимального кодирования.
Ил. 2, библиогр. 12.
Л. П. Жильцова 1
1. Нижегородский государственный педагогический университет,
ул. Ульянова, 1, 603005 Нижний Новгород, Россия
Статья поступила 6 июня 2001 г.
