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.
R.Alur and D.L.Dill, A theory of timed automata, Theoretical Computer Science126(2) (1994), 183–235.
3.
E.Asarin and A.Degorre, Volume and entropy of regular timed languages: Discretization approach, in: CONCUR, 2009, pp. 69–83.
4.
N.Chomsky and G.A.Miller, Finite state languages, Information and Control1 (1958), 91–112.
5.
T.M.Cover and J.A.Thomas, Elements of Information Theory, 2nd edn, Wiley-Interscience, 2006.
6.
C.Cui, Z.Dang and T.R.Fischer, Bit rate of programs, CoRR, 2013.
7.
C.Cui, Z.Dang, T.R.Fischer and O.H.Ibarra, Similarity in languages and programs, Theor. Comput. Sci.498 (2013), 58–75.
8.
C.Cui, Z.Dang, T.R.Fischer and O.H.Ibarra, Information rate of some classes of non-regular languages: An automata-theoretic approach, in: MFCS’14, Lecture Notes in Computer Science, Vol. 8634, Springer, 2014.
9.
Z.Dang, Pushdown timed automata: A binary reachability characterization and safety verification, Theor. Comput. Sci.1–3(302) (2003), 93–121.
10.
Z.Dang, O.H.Ibarra, T.Bultan, R.A.Kemmerer and J.Su, Binary reachability analysis of discrete pushdown timed automata, in: CAV’00: Proceedings of International Conference on Computer Aided Verification, Lecture Notes in Computer Science, Vol. 1855, Springer, 2000, pp. 69–84.
11.
Z.Dang, O.H.Ibarra and Q.Li, Sampling a two-way finite automaton, in: Emergence, Complexity and Computation, Automata, Universality, Computation, Vol. 12, Springer, 2014.
12.
E.M.Gurari and O.H.Ibarra, The complexity of decision problems for finite-turn multicounter machines, Journal of Computer and System Sciences22 (1981), 220–229.
13.
E.M.Gurari and O.H.Ibarra, A note on finite-valued and finitely ambiguous transducers, Math. Systems Theory16 (1983), 61–66.
14.
J.E.Hopcroft, R.Motwani and J.D.Ullman, Introduction to Automata Theory, Languages, and Computation, 1st edn, Addison-Wesley, 1979.
15.
O.H.Ibarra, Reversal-bounded multicounter machines and their decision problems, Journal of the ACM25(1) (1978), 116–133.
16.
O.H.Ibarra, Z.Dang, O.Egecioglu and G.Saxena, Characterizations of catalytic membrane computing systems, in: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science, Vol. 2747, Springer, 2003, pp. 480–489.
17.
F.P.Kaminger, The noncomputability of the channel capacity of context-sensitive languages, Inf. Comput.17(2) (1970), 175–182.
18.
W.Kuich, On the entropy of context-free languages, Information and Control16(2) (1970), 173–200.
19.
Q.Li and Z.Dang, Sampling automata and programs, Theoretical Computer Science577 (2015), 125–140.
20.
G.Paun, Membrane Computing, an Introduction, Springer-Verlag, 2002.
21.
M.P.Schützenberger, Sur les Relations Rationnelles, in: Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20–23, 1975Lecture Notes in Comput. Sci., Vol. 33, 1975, pp. 209–213.
22.
C.E.Shannon and W.Weaver, The Mathematical Theory of Communication, University of Illinois Press, 1949.
23.
L.Staiger, The entropy of Lukasiewicz-languages, in: Revised Papers from the 5th International Conference on Developments in Language Theory, DLT’01, Springer-Verlag, London, UK, 2002, pp. 155–165.
24.
E.Wang, C.Cui, Z.Dang, T.R.Fischer and L.Yang, Zero-knowledge blackbox testing: Where are the faults, Int’l. J. Foundations of Computer Science25(2) (2014), 196–218.
25.
A.Weber, On the valuedness of finite transducers, Acta Inf.27(9) (1990), 749–780.
26.
K.Wich, Ambiguity functions of context-free grammars and languages, PhD thesis, 2004.
27.
G.Xie, Z.Dang and O.H.Ibarra, A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems, in: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science, Vol. 2719, Springer, 2003, pp. 668–680.
28.
L.Yang, C.Cui, Z.Dang and T.R.Fischer, An information-theoretic complexity metric for labeled graphs, 2011, in review.
