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

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