VALIDATION OF THE TRANSMITTER’S BEHAVIOUR IN THE PARTIAL ERASURE CHANNEL IN THE CASE OF ABSENCE OF ABSOLUTELY DISTINGUISHABLE CHARACTERS

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 a1, a2 ∈ 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 ∈ 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 Fˆ : S ∗ → A∗ as follows: for any word ˆs ∈ S ∗ , ˆs = s1 . . . sm, let Fˆ(ˆs) = F(Λ)F(s1)F(s1s2). . . F(s1 . . . sm), where Λ is the empty word. The function Fˆ 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 ∈ S and the word α ∈ 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, sˆ2) such that |sˆ2| = |sˆ1| + 1, |Fˆ(ˆs2)| 6 |Fˆ(ˆs1)|. The anomaly of the first kind is a pair of words (ˆs1, sˆ2) such that there is an index i such that the characters Fˆ(ˆs1)[i] and Fˆ(ˆs2)[i] 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.