A validation algorithm of the transmitter's boundedly deterministic behaviour in a partial erasure channel

In the previous papers, the notions of a partial erasure structure and a partial erasure channel have been introduced. A partial erasure structure is a triplet consisting of an alphabet $A$, a family of partitions of the alphabet and a set of probabilities assigned to the partitions. A partial erasure channel functions as follows. Alice sends Bob a symbol $a \in A$, but Bob receives only partial information about the symbol. Bob only knows which partition has been choosen and which class of the partition the symbol belongs to. The set of pairs consisting of a partition and a class of the partition, i.e., the signals Bob can receive, is denoted as Bob's alphabet $B$. There is a natural correspondence between the characters sent by Alice and received by Bob. For symbols $a \in A$ and $b \in B$, $a \mapsto b$ is assumed to hold if there exists a partition $T$ in the partial erasure structure such that $b = (\pi_T(a), T )$. The correspondence is also generalized to the words. We assume that $a_1 \ldots a_n \mapsto b_1 \ldots b_n$ holds, if $a_i \mapsto b_i$ holds for all $i = 1 \ldots n$. Suppose that Alice has an input tape from which she reads symbols of some finite alphabet $S$. Bob has an output tape, on which he can print symbols of alphabet $S$ and also specially reserved (not in $S$) erasure symbol “*”. Thus, a problem of transmitting information via the descibed channel (i.e., a problem of construction of Alice's and Bob's behaviour) arises. In the previous papers of the author, a formal model of interaction between a transmitter (Alice) and a receiver (Bob), called a protocol, is presented. A protocol is a pair of functions $(F, G)$, where $F: S^{*} \to A^{*}$ is the Alice behaviour function and $G: B^{*} \to S \cup \{*, \Lambda\}$ is the Bob behaviour function. Suppose that Alice has just read another symbol $s \in S$ from the input tape, having previously read the word $\hat{s} = s_1, \ldots, s_m$. Then we assume that during the following $|F (\hat{s} s)|$ steps Alice sends the word $F(\hat{s} s)$ symbol by symbol via the channel of partial erasure. Bob receives the symbol $b \in B$ on each step. After receiving the symbol, he has to decide what to print on the output tape. He can print a symbol of the alphabet $S$, or the erasure symbol “*”, or nothing. Bob's decision is determined by the function $G$. The protocol $(F, G)$ is said to be valid, if Bob prints on the output tape the same content what originally is on the input tape, while, perhaps, with the replacement of the significant symbols (i.e., the symbols of the alphabet $S$) to the erasure symbol “*”. Among all Alice's behavior functions, a class of correct functions is defined. A function $F$ is said to be correct, if $F(\Lambda) F(s^1_1) F(s^1_1 s^1_2) \ldots F(s^1_1 \ldots s^1_n) \mapsto \beta_1$, $F(\Lambda) F(s^2_1) F(s^2_1 s^2_2) \ldots F(s^2_1 \ldots s^2_m) \mapsto \beta_2$ and $\beta_1$ is a prefix to $\beta_2$, where $\beta_1, \beta_2\in B^*$. The question is investigated, for which functions of Alice's behavior $F$ there exists a function of Bob's behavior $G$ such that the pair $(F, G)$ is a correct protocol. The theorem is proved that for this it is necessary and sufficient that $F$ belongs to the class of correct functions. This paper presents an algorithm for verifying that Alice's behavior function $F$ belongs to the class of correct functions. The complexity of the algorithm is $O(L |Q|^3 |S|^4 )$, 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, $|S|$ is the number of symbols of the alphabet $S$.