Affiliations: [a] Department of Computer Science, University of California, Santa Barbara, CA 93106, USA. ibarra@cs.ucsb.edu | [b] School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA. ccui@eecs.wsu.edu | [c] School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA. zdang@eecs.wsu.edu | [d] School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA. fischer@eecs.wsu.edu
Note: [1] A conference version of this paper is in the proceeding of CiE 2014.
Abstract: We provide an automata-theoretic approach to analyzing an abstract channel modeled by a transducer and to characterizing its lossy rates. In particular, we look at related decision problems and show the boundaries between the decidable and undecidable cases. We conduct experiments on several channels and use Lempel–Ziv algorithms to estimate lossy rates of these channels.
Keywords: Automata, transducers, Shannon information
DOI: 10.3233/COM-150050
Journal: Computability, vol. 6, no. 2, pp. 165-181, 2017
