RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1990, том 2, выпуск 2, страницы 3–15 (Mi dm846)

Системы уравнений антипрефиксности в слолах

А. А. Марков


Аннотация: Отношение антипрефиксности на множестве слов $\diagdown\!\!\!\!\!\--$ означает, что $\alpha$ и $\beta$ различны и никакое из них не является префиксом (левым отрезком) другого. Соотношение $f\,\diagdown\!\!\!\!\!\!\--g$ называется уравнением антипрефиксности в словах, если $f$ и $g$ – слова в алфавите $A\cup X$, где $A$ – произвольный фиксированный алфавит, а $X$ – алфавит неизвестных. Системами уравнений антипрефиксности в словах описываются дешифруемые с конечной задержкой коды для различных структурных моделей языков. Теория систем уравнений антипрефиксности включает в себя теорию префиксных кодов и теорию правильных раскрасок графов. В работе приведены оценки сложности множеств решений систем уравнений антипрефиксности.

УДК: 519.68

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


 Англоязычная версия: Discrete Mathematics and Applications, 1992, 2:1, 11–24

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


© МИАН, 2024