

Principle Seminar of the Department of Probability Theory, Moscow State University
September 21, 2016 16:45, Moscow, MSU, auditorium 1224






Separating codes
I. V. Vorob'ev^{} ^{} Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Number of views: 
This page:  38 

Abstract:
A binary code of length $N$ and size $t$ is said to be a separating $(s, l)$code if it is an incidence matrix of a family
of $t$ subsets of an $N$set where for every two disjoint sets of subsets of a family $S$ and $L$ with cardinalities $s$
and $l$ there is an element of the original $N$set such that either it belongs to every subset from S and doesn't
belong to any subset from $L$, or it belongs to every subset from $L$ and doesn't belong to any subset from $S$.
The purpose of this dissertation is to establish new asymptotic lower and upper bounds on the maximal
cardinality $t(N, s, l)$ of binary separating $(s, l)$codes and their generalization called $q$ary separating
$(s, l)$codes, which are used in automata theory, digital fingerprinting and some other applied problems of
information theory and coding theory.

