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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Dill, D.L.: A theory of timed automata. Theoretical Computer Science 126(2), 183–235 (1994)
Asarin, E., Degorre, A.: Volume and entropy of regular timed languages: Discretization approach. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 69–83. Springer, Heidelberg (2009)
Chomsky, N., Miller, G.A.: Finite state languages. Information and Control 1, 91–112 (1958)
Cui, C., Dang, Z., Fischer, T.R.: Bit rate of programs (2013) (submitted)
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Similarity in languages and programs. Theor. Comput. Sci. 498, 58–75 (2013)
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Information rate of some classes of non-regular languages: An automata-theoretic approach (submitted, 2014)
Dang, Z.: Pushdown timed automata: a binary reachability characterization and safety verification. Theor. Comput. Sci. 302(1-3), 93–121 (2003)
Dang, Z., Ibarra, O.H., Bultan, T., Kemmerer, R.A., Su, J.: Binary reachability analysis of discrete pushdown timed automata. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 69–84. Springer, Heidelberg (2000)
Dang, Z., Ibarra, O.H., Li, Q.: Sampling a two-way finite automaton (submitted, 2014)
Gurari, E.M., Ibarra, O.H.: A note on finite-valued and finitely ambiguous transducers. Math. Systems Theory 16, 61–66 (1983)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 1st edn. Addison-Wesley (1979)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. Journal of the ACM 25(1), 116–133 (1978)
Ibarra, O.H., Dang, Z., Egecioglu, O., Saxena, G.: Characterizations of Catalytic Membrane Computing Systems. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 480–489. Springer, Heidelberg (2003)
Kaminger, F.P.: The noncomputability of the channel capacity of context-senstitive languages. Inf. Comput. 17(2), 175–182 (1970)
Kuich, W.: On the entropy of context-free languages. Information and Control 16(2), 173–200 (1970)
Li, Q., Dang, Z.: Sampling automata and programs (2013) (submitted)
Paun, G.: Membrane Computing, An Introduction. Springer (2002)
Schützenberger, M.P.: Sur les relations rationnelles. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 209–213 (1975)
Shannon, C.E., Weaver, W.: The Mathematical Theory of Communication. University of Illinois Press (1949)
Staiger, L.: The entropy of lukasiewicz-languages. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 155–165. Springer, Heidelberg (2002)
Wang, E., Cui, C., Dang, Z., Fischer, T.R., Yang, L.: Zero-knowledge blackbox testing: Where are the faults. Int’l J. Foundations of Computer Science (to appear)
Weber, A.: On the valuedness of finite transducers. Acta Inf. 27(9), 749–780 (1990)
Wich, K.: Ambiguity functions of context-free grammars and languages. PhD thesis (2004)
Xie, G., Dang, Z., Ibarra, O.H.: A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 668–680. Springer, Heidelberg (2003)
Yang, L., Cui, C., Dang, Z., Fischer, T.R.: An information-theoretic complexity metric for labeled graphs (2011) (in review)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ibarra, O.H., Cui, C., Dang, Z., Fischer, T.R. (2014). Lossiness of Communication Channels Modeled by Transducers. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds) Language, Life, Limits. CiE 2014. Lecture Notes in Computer Science, vol 8493. Springer, Cham. https://doi.org/10.1007/978-3-319-08019-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-08019-2_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08018-5
Online ISBN: 978-3-319-08019-2
eBook Packages: Computer ScienceComputer Science (R0)