Abstract
Most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. This work presents an upper bound on the length of the shortest synchronizing string for such codes. Two classes of codes with a long shortest synchronizing string are presented. It is known that finding a synchronizing string for a code is equivalent to a finding a synchronizing string of some finite automaton. The Černý conjecture for this class of automata is discussed.
The research was partially supported by the grants of the Polish Ministry of Science and Higher Education N 206 004 32/0806 and N N206 376134.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Capocelli, R.M., Gargano, L., Vaccaro, U.: On the characterization of statistically synchronizable variable-length codes. IEEE Trans. Inform. Theory 34(4), 817–825 (1988)
Freiling, C.F., Jungreis, D.S., Theberge, F., Zeger, K.: Almost all complete binary prefix codes have a self-synchronizing string. IEEE Trans. Inform. Theory 49(9), 2219–2225 (2003)
Schützenberger, M.P.: On synchronizing prefix codes. Information and Control 11(4), 396–401 (1967)
Rudner, B.: Construction of minimum-redundancy codes with an optimum synchronizing property. IEEE Trans. Inform. Theory 17(4), 478–487 (1971)
Perkins, S., Escott, A.E.: Synchronizing codewords of q-ary Huffman codes. Discrete Math. 197-198, 637–655 (1999)
Huang, Y.M., Wu, S.C.: Shortest synchronizing codewords of a binary Huffman equivalent code. In: ITCC 2003: Proceedings of the International Conference on Information Technology: Computers and Communications, Washington, DC, USA, p. 226. IEEE Computer Society Press, Los Alamitos (2003)
Capocelli, R.M., Santis, A.D., Gargano, L., Vaccaro, U.: On the construction of statistically synchronizable codes. IEEE Trans. Inform. Theory 38(2), 407–414 (1992)
Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inform. Theory 30(4), 687–693 (1984)
Maxted, J.C., Robinson, J.P.: Error recovery for variable length codes. IEEE Trans. Inform. Theory 31(6), 794–801 (1985)
Černý, J.: Poznámka k. homogénnym experimentom s konecnými automatmi. Mat. fyz.cas SAV 14, 208–215 (1964)
Ananichev, D.S., Volkov, M.V.: Synchronizing generalized monotonic automata. Theor. Comput. Sci. 330(1), 3–13 (2005)
Kari, J.: Synchronizing finite automata on eulerian digraphs. Theor. Comput. Sci. 295(1-3), 223–232 (2003)
Pin, J.E.: On two combinatorial problems arising from automata theory. Annals of Discrete Mathematics 17, 535–548 (1983)
Ananichev, D.S., Volkov, M.V., Zaks, Y.I.: Synchronizing automata with a letter of deficiency 2. Theor. Comput. Sci. 376(1-2), 30–41 (2007)
Trahtman, A.N.: An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture. In: Kralovic, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 789–800. Springer, Heidelberg (2006)
Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500–510 (1990)
Sandberg, S.: Homing and Synchronizing Sequences. In: Broy, M., Jonsson, B., Katoen, J.P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5–33. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Biskup, M.T. (2008). Shortest Synchronizing Strings for Huffman Codes. In: Ochmański, E., Tyszkiewicz, J. (eds) Mathematical Foundations of Computer Science 2008. MFCS 2008. Lecture Notes in Computer Science, vol 5162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85238-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-85238-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85237-7
Online ISBN: 978-3-540-85238-4
eBook Packages: Computer ScienceComputer Science (R0)