Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2023, Number 59, Pages 88–110
DOI: https://doi.org/10.17223/20710410/59/6
(Mi pdm796)
 

Computational Methods in Discrete Mathematics

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

I. B. Kazakov

Moscow Institute of Physics and Technology, Dolgoprudny, Russia
References:
Abstract: 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$.
Keywords: covert channels, partial erasure structure, partial erasure channel, information transmission protocol, check algorithm.
Document Type: Article
UDC: 519.726
Language: Russian
Citation: I. B. Kazakov, “A validation algorithm of the transmitter's boundedly deterministic behaviour in a partial erasure channel”, Prikl. Diskr. Mat., 2023, no. 59, 88–110
Citation in format AMSBIB
\Bibitem{Kaz23}
\by I.~B.~Kazakov
\paper A validation algorithm of the transmitter's boundedly deterministic behaviour in a partial erasure channel
\jour Prikl. Diskr. Mat.
\yr 2023
\issue 59
\pages 88--110
\mathnet{http://mi.mathnet.ru/pdm796}
\crossref{https://doi.org/10.17223/20710410/59/6}
Linking options:
  • https://www.mathnet.ru/eng/pdm796
  • https://www.mathnet.ru/eng/pdm/y2023/i1/p88
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:103
    Full-text PDF :28
    References:23
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024