RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2003, том 10, выпуск 3, страницы 23–53 (Mi da136)

Закономерности в деревьях вывода слов стохастического контекстно-свободного языка и нижняя оценка стоимости кодирования. Критический случай

Л. П. Жильцова

Нижегородский государственный педагогический университет

Аннотация: Рассматривается язык, порожденный стохастической контекстно-свободной грамматикой, матрица первых моментов которой неразложима, непериодична и ее перронов корень равен 1. Для такого языка установлены закономерности в деревьях вывода фиксированной высоты $t$ при $t\to\infty$. На основе этих закономерностей получена точная нижняя оценка стоимости двоичного кодирования.

УДК: 519.713

Статья поступила: 29.04.2003



Реферативные базы данных:


© МИАН, 2024