On infinitary finite length codes. (English) Zbl 0628.68056

The paper investigates the relations between the following four properties of codes C over a finite alphabet X: (i) For all words \(u,v\in X^*\) and for every \(w\in C^*:\) \(wu,uv,vu\in C^*\) implies \(u,v\in C^*\). (ii) Every one-sided infinite product of words of C is unambiguous. (iii) C has finite decoding delay. (iv) C has bounded decoding delay.
As is well-known, these four properties are equivalent for finite codes. The paper shows that in general only (iv)\(\to (iii)\to (ii)\to (i)\) holds, whereas none of the reverse implications is true.
To this end several characterizations of the classes of codes defined by the above conditions are given. Counterexamples to the implications (iii)\(\to (iv)\) and (ii)\(\to (iii)\) are derived by topological arguments utilizing properties of \(C^{\omega}\) in the space \(X^{\omega}\) of all \(\omega\)-words over X. The last section deals with infinite regular codes for which the reverse implications (i)\(\to (ii)\) and (iii)\(\to (iv)\) are proved to be true, whereas (ii)\(\to (iii)\) does not hold.


68Q45 Formal languages and automata
94A45 Prefix, length-variable, comma-free codes
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI EuDML


[1] BN. L. BOASSON and M. NIVAT, Adherences of languages, J. Comput. System Sci., Vol. 20, 1980, pp. 285-309. Zbl0471.68052 MR584863 · Zbl 0471.68052 · doi:10.1016/0022-0000(80)90010-0
[2] C 1. R. M. CAPOCELLI, A note on uniquely decipherable codes, IEEE Trans. Information Theory, vol. IT-25, 1979, pp. 90-94. Zbl0388.94015 MR514936 · Zbl 0388.94015 · doi:10.1109/TIT.1979.1056005
[3] C2. R. M. CAPOCELLI, On weakly prefix subsemigroups of a free semigroup in: Advances in Communications, D. G. LAINIOTIS and N. S. TSANNES, Eds, D. Reidel, Dordrecht 1980, pp. 123-129. Zbl0474.94032 MR615938 · Zbl 0474.94032
[4] Da. M. DAVIS, Infinite games of perfect Information, in: Advances in Game Theory. Ann. of Mathematical Studies, No. 52, 1964, pp. 85-101. Zbl0133.13104 MR170727 · Zbl 0133.13104
[5] D 1. Do L. V., Codes avec des mots infinis. RAIRO Inform. Theor., Vol. 16, 1982, pp. 371-386. Zbl0498.68053 MR707638 · Zbl 0498.68053
[6] D 2. Do L. V., Sous-monoides et codes avec des mots infinis, Semigroup Forum, Vol. 26, 1983, pp. 75-87. Zbl0504.68054 MR685117 · Zbl 0504.68054 · doi:10.1007/BF02572821
[7] D 3. Do L. V., Contribution to combinatorics on words, Diss. B. Humboldt-Univ., Berlin, 1985.
[8] DK. P. DARONDEAU and L. KOTT, A formal proof System for infinitary rational expressions in: Automata on Infinite Words, M. NIVAT and D. PERRIN Eds, Lecture Notes in Computer Science, No. 192, Springer-Verlag, Berlin 1985, pp. 68-80. Zbl0575.68083 MR814733 · Zbl 0575.68083
[9] L. V. I. LEVENSHTEIN, Some properties of coding and self adjusting automata for decoding messages, Problemy Kibernetiki, Vol. 11, 1964, pp. 63-121. Zbl0235.94002 MR168396 · Zbl 0235.94002
[10] LS. R. LINDER und L. STAIGER, Algebraische Codierungstheorie-Theorie der sequentiellen Codierungen, Akademie-Verlag, Berlin 1977. Zbl0363.94016 MR469495 · Zbl 0363.94016
[11] Sc. N. P. SCHÜTZENBERGER, On a question concerning certain free submonoids, J. Combinatorial Theory, Vol. 1, 1966, pp. 437-442. Zbl0158.02302 MR218145 · Zbl 0158.02302 · doi:10.1016/S0021-9800(66)80015-7
[12] Sh. St J. SHYR, Free Monoids and Languages, Lecture Notes, Soochow Univ., Taipei, 1979. Zbl0407.68076 · Zbl 0407.68076
[13] S 1. L. STAIGER, Eine Bemerkung zur Charakterisierung von Folgenmengen durch Wortmengen, Elektron. Inf. verarb. Kybernetik, Vol. 8, 1972, pp. 589-592. Zbl0336.94036 MR345457 · Zbl 0336.94036
[14] S 2. L. STAIGER, Zur Topologie der regulären Mengen, Diss. A., Friedrich-Schiller-Univ., Jena, 1976.
[15] S 3. L. STAIGER, A note on connected \omega -languages, Elektron. Inf. verarb. Kybernetik, Vol. 16, 1980, pp. 245-251. Zbl0452.68085 · Zbl 0452.68085
[16] W. K. WAGNER, On \omega -regular sets, Information and Control, Vol. 43, 1979, pp. 123-177. Zbl0434.68061 · Zbl 0434.68061 · doi:10.1016/S0019-9958(79)90653-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.