PUB - Publikationen an der Universität Bielefeld

For the discrete memoryless channel (X, Y, W) we give characterizations of the zero-error erasure capacity C-er and the zero-error average list size capacity C-al in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not ''single-letterize.'' Next we assume that X subset of Y and W(x/x) > 0 for all x is an element of X, and we associate with W the low-noise channel W-epsilon, where for Y+ (x) = {y : W(y/x) > 0} [GRAPHICS] Our Theorem 2 says that as epsilon tends to zero the capacities C-er(W-epsilon) and C-al(W-epsilon) relate to the zero-error detection capacity C-de(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C-oid for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C-oid equals the zero-error erasure capacity for transmission C-er.