PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Coding with Noiseless Feedback
V. S. Lebedev
pp. 103–113

Abstract—We consider the problem of error correction using nonbinary codes and assuming noiseless feedback. This is equivalent to the searching with lies problem. We improve the algorithm proposed by Ahlswede, Deppe, and Lebedev in [1].

Generalized Preparata Codes and 2-Resolvable Steiner Quadruple Systems
V. A. Zinoviev and D. V. Zinoviev
pp. 114–133

Abstract—We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce $2$-resolvable Steiner quadruple systems $S(n,4,3)$ (i.e., systems $S(n,4,3)$ that can be partitioned into disjoint Steiner systems $S(n,4,2)$). The obtained partitions of systems $S(n,4,3)$ into systems $S(n,4,2)$ are not equivalent to such partitions previously known.

Some New Results on Hadamard Modulo Prime Matrices
Y. L. Borissov
pp. 134–141

Abstract—First, some nonexistence and classification results on Hadamard modulo prime matrices whose size is relatively small with respect to their modulus, are presented. Second, we show the existence of an infinite class of matrices of that kind derived by finite projective planes.

Almost Cover-Free Codes
N. A. Polyansky
pp. 142–155

Abstract—We say that an $s$-subset of codewords of a code $X$ is $(s,\ell)$-bad if $X$ contains $\ell$ other codewords such that the conjunction of these $\ell$ words is covered by the disjunction of the words of the $s$-subset. Otherwise, an $s$-subset of codewords of $X$ is said to be $(s,\ell)$-good. A binary code $X$ is called a disjunctive $(s,\ell)$ cover-free (CF) code if $X$ does not contain $(s,\ell)$-bad subsets. We consider a probabilistic generalization of $(s,\ell)$ CF codes: we say that a binary code is an $(s,\ell)$ almost cover-free (ACF) code if almost all $s$-subsets of its codewords are $(s,\ell)$-good. The most interesting result is the proof of a lower and an upper bound for the capacity of $(s,\ell)$ ACF codes; the ratio of these bounds tends as $s\to\infty$ to the limit value $\log_2e/(\ell e)$.

Doubly Randomized Protocols for a Random Multiple Access Channel with “Success–Nonsuccess” Feedback
S. G. Foss, B. Hajek, and A. M. Turlikov
pp. 156–165

Abstract—We consider a model of a decentralized multiple access system with a nonstandard binary feedback where the empty and collision situations cannot be distinguished. We show that, like in the case of a ternary feedback, for any input rate $\lambda\lt e^{-1}$ there exists a “doubly randomized” adaptive transmission protocol which stabilizes the behavior of the system. We discuss also a number of related problems and formulate some hypotheses.

On Interval Modal Logic with “After” Relation
A. S. Chizhov
pp. 166–177

Abstract—This paper is devoted to study of the logic corresponding to intervals of the real line, where the modality is interpreted as “after.” Since this logic is finitely axiomatizable, the proof of the finite model property given in the paper implies its decidability. Also, a description of the class of finite rooted Kripke frames corresponding to this logic is provided.

Queueing Networks with Mobile Servers: The Mean-Field Approach
F. Baccelli, A. N. Rybko, and S. B. Shlosman
pp. 178–199

Abstract—We consider queueing networks which are made from servers exchanging their positions on a graph. When two servers exchange their positions, they take their customers with them. Each customer has a fixed destination. Customers use the network to reach their destinations, which is complicated by movements of the servers. We develop the general theory of such networks and establish the convergence of the symmetrized version of such a network to some nonlinear Markov process.

Erratum to: “Bounds on the Rate of Disjunctive Codes” [Problems of Information Transmission 50, 27 (2014)]
A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, and V. Yu. Shchukin
p. 200

In the proof of Theorem 4, by the authors' fault, an error was made in the derivation of equation (60). Therefore, Theorem 4 remains unproved; the same concerns Theorems 2 and 5, the proofs of which are based on the result of Theorem 4.