Валидация поведения передатчика в канале частичного стирания в случае отсутствия абсолютно различимых символов | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/4

Работа принадлежит циклу работ, посвящённых каналу частичного стирания, где были введены понятия структуры частичного стирания, канала частичного стирания, правильной функции и корректного протокола. Структура частичного стирания - это тройка, состоящая из алфавита A, семейства его разбиений и множества вероятностей, приписанных этим разбиениям. Символы ai,02 G A называются абсолютно различимыми в структуре частичного стирания, если не существует такого разбиения, что они принадлежат одному его классу. Канал частичного стирания функционирует следующим образом: Алиса посылает Бобу символ а G A, но Боб узнаёт только, какое выбрано разбиение и какому классу принадлежит отправленный Алисой символ. Поведение передатчика в канале частичного стирания задаётся функцией F : S* A*, где S - алфавит входной ленты, с которой передатчик считывает информацию. Функция F однозначно определяет детерминированную функцию F : S* A*: для любого слова s G S*, s = s1 ...sm, положим ]s{s) = F (A)F (s1)F (s1 s2) ...F (s1 ...sm), где Л - пустое слово. Функция Fs может быть представлена в виде автомата с входным алфавитом S и выходным алфавитом A*. Автомат задаётся графом, вершины которого соответствуют состояниям, а рёбра имеют две подписи: s G S и а G A*. Для существования корректного протокола, включающего в себя функцию F поведения передатчика, необходимо и достаточно принадлежности функции F к классу правильных. Функция является правильной тогда и только тогда, когда отсутствует аномалия 2-го рода, не являющаяся также и аномалией 1-го рода. Под аномалией 2-го рода понимается пара слов (S1, S2), такая, что |S2| = |S1| +1, |F(S2)| |F(S1)|; под аномалией 1-го рода -пара слов (S1,S2), для которой найдётся индекс i, что символы F(S1)[i] и F(S2)[i] абсолютно различимы в структуре частичного стирания. В важном частном случае отсутствия абсолютно различимых символов аномалии 1-го рода не могут существовать и условие правильности упрощается до отсутствия аномалий 2-го рода. Показано, что проверка отсутствия аномалий 2-го рода сводится к проверке отсутствия путей (начинающихся в выделенной вершине) отрицательного веса в автомат-квадратном графе, которая может быть выполнена с помощью алгоритма Беллмана - Форда. Общая сложность такой проверки составляет O(|Q|4|S|2) по времени и O(|Q|2|S|2 In |Q| In L In |S|) по памяти, где |Q| - количество состояний автомата, представляющего функцию , и L - максимальная длина передаваемого Алисой слова.