Validation of the transmitter's behaviour in the partial erasure channel in the case of absence of absolutely distinguishable characters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 67. DOI: 10.17223/20710410/67/4

This paper belongs to a series of papers devoted to the partial erasure channel, in which the concepts of partial erasure structure, partial erasure channel, correct function, and correct protocol have been introduced. The partial erasure structure is a triple consisting of the alphabet A, a family of partitions of this alphabet, and a set of probabilities attributed to the partitions. The characters ai,a2 G A are called absolutely distinguishable if there is no partition such that they belong to the same class of this partition. The partial erasure channel functions as follows. Alice sends Bob a symbol a G A, but Bob receives only partial information about the symbol. Bob only knows which partition has been choosen and which partition class the symbol belongs to. The behavior of the transmitter in the partial erase channel can be described by specifying a function F : S* A*, where S is the alphabet of the input tape from which the transmitter reads information. The function F uniquely defines the deterministic function : S* A* as follows: for any word s G S*, ,§ = s1.. .sm, let i(S) = F(Л)F(s1)F(s1s2)... F(s1... sm), where Л is the empty word. The function Fs can be represented as an automaton with the input alphabet S and the output alphabet A*. The automaton, in turn, is represented as a graph whose vertices correspond to states and edges have two signatures: the symbol s G S and the word a G A*. For the existence of a correct protocol that includes the function F of the transmitter behavior, it is necessary and sufficient that the function F belongs to the class of correct functions. A function is correct if and only if there is no anomaly of the second kind, which is not an anomaly of the first kind. The anomaly of the second kind is a pair of words (S1,S2) such that |S2| = |S1| + 1, |(S2)| |(S1)|. The anomaly of the first kind is a pair of words (S1,S2) such that there is an index i such that the characters (S1 )[i] and (S2)[ij are absolutely distinguishable. In the important special case of the absence of absolutely distinguishable symbols, anomalies of the first kind cannot exist. Therefore, the correctness condition is simplified to the absence of anomalies of the second kind. In this paper, it is shown that checking for the absence of anomalies of the second kind is reduced to checking for the absence of paths (starting at the selected vertex) of negative weight in the so-called automaton-square graph. This absence can be detected by the Bellman - Ford algorithm. The total complexity of checking for the absence of anomalies of the second kind is O(|Q|4|S|2) in time and O(|Q|2|S|2 ln |Q| lnLln |S|) in memory, where |Q| is the number of states of the automaton representing the function F, L is the maximum length of the word Alice throws out.