ERASURE, LIST, AND DETECTION ZERO-ERROR CAPACITIES FOR LOW-NOISE AND A RELATION TO IDENTIFICATION

For the discrete memoryless channel (X, Y, W) we give characterization s of the zero-error erasure capacity C-er and the zero-error average l ist size capacity C-al in terms of limits of suitable information (res pectively, divergence) quantities (Theorem 1). However, they do not '' single-letterize.'' Next we assume that X subset of Y and W(x/x) > 0 f or all x is an element of X, and we associate with W the low-noise cha nnel W-epsilon, where for Y+ (x) = {y : W(y/x) > 0} [GRAPHICS] Our The orem 2 says that as epsilon tends to zero the capacities C-er(W-epsilo n) and C-al(W-epsilon) relate to the zero-error detection capacity C-d e(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) ident ification capacity C-oid for identification codes with zero misrejecti on probability and misacceptance probability tending to zero. Our Theo rem 3 says that C-oid equals the zero-error erasure capacity for trans mission C-er.