A completion algorithm for codes with bounded synchronization delay

1. R.L. Adler, D. Coppersmith, and M. Hassner. Algorithms for sliding block codes. IEEE Trans. Inform. Theory, IT-29:5–22, 1983.

   Article  Google Scholar 

2. D. Arquès and C. Michel. A possible code in the genetic code. In STACS'95 Proceedings, volume 900 of Lecture Notes in Comput. Sci., pages 640–651, 1995.

   Google Scholar 

3. J. Ashley, B. Marcus, D. Perrin, and S. Tuncel. Surjective extensions of sliding block codes. SIAM J. Discrete Math., 6:582–611, 1993.

   Article  Google Scholar 

4. F. Bassino. Séries rationnelles et distributions de longueurs. PhD thesis, University of Marne-La-Vallée, 1996.

   Google Scholar 

5. M.-P. Béal. The method of poles: a coding method for constrained channels. IEEE Trans. Inf. Theory, 36:763–772, 1990.

   Article  Google Scholar 

6. M.-P. Béal. Codage symbolique. Masson, 1993.

   Google Scholar 

7. J. Berstel and D. Perrin. Theory of codes. Academic Press, 1985.

   Google Scholar 

8. J. Berstel and D. Perrin. Trends in the theory of codes. Bull. EATCS, 29:84–95, 1986.

   Google Scholar 

9. V. Bruyère and M. Latteux. Variable-length maximal codes. In ICALP'96 Proceedings, volume 1099 of Lecture Notes in Comput. Sci., pages 24–47, 1996.

   Google Scholar 

10. V. Bruyère, L. Wang, and L. Zhang. On completion of codes with finite deciphering delay. European J. Combin., 11:513–521, 1990.

    Google Scholar 

11. J. Devolder. Codes, mots infinis et bi-infinis. PhD thesis, University of Lille I, 1993.

    Google Scholar 

12. J. Devolder. Precircular codes and periodic biinfinite words. Inf. Comput., 107:185–201, 1993.

    Article  Google Scholar 

13. G. Duchamp and J.-Y. Thibon. Bisections reconnaissables. RAIRO Inform. Théor. Appl., 22:113–128, 1988.

    Google Scholar 

14. A. Ehrenfeucht and G. Rozenberg. Each regular code is included in a regular maximal code. RAIRO Inform. Théor. Appl., 20:89–96, 1985.

    Google Scholar 

15. P.A. Franaszek. A general method for channel coding. IBM J. Res. Dev., 24:638–641, 1980.

    Google Scholar 

16. S.W. Gordon and B. Gordon. Codes with bounded synchronization delay. Inf. Control, 8:355–372, 1965.

    Article  Google Scholar 

17. H. Jürgensen and S. Konstantinidis. Handbook of Formal Languages, chapter Codes. Springer-Verlag, 1997. to appear.

    Google Scholar 

18. D. Krob. Codes limités et factorisations finies du monoïde libre. RAIRO Inform. Théor. Appl., 21:437–467, 1987.

    Google Scholar 

19. N.H. Lam. On codes having no finite completions. preprint, 1996.

    Google Scholar 

20. V.I. Levenshtein. Some properties of coding and self-adjusting automata for decoding messages. Problemy Kibernet., 11:63–121, 1964.

    Google Scholar 

21. D. Lind and B. Marcus. Symbolic Dynamics and Coding. Cambridge University Press, 1996.

    Google Scholar 

22. R. Montalbano. Local automata and completion. In STACS'93 Proceedings, volume 665 of Lecture Notes in Comput. Sci., pages 333–342, 1993.

    Google Scholar 

23. D. Perrin. Completing biprefix codes. Theoret. Comput. Sci., 28:329–336, 1984.

    Article  Google Scholar 

24. D. Perrin and M.-P. Schützenberger. Un problème élémentaire de la théorie de l'information. In Théorie de l'Information, Colloques Internat. CNRS, volume 276, pages 249–260, Cachan, 1977.

    Google Scholar 

25. A. Restivo. On a question of McNaughton and Papert. Inf. Control, 1:1, 1974.

    Google Scholar 

26. A. Restivo. A combinatorial property of codes having finite synchronization delay. Theoret. Comput. Sci., 1:95–101, 1975.

    Article  Google Scholar 

27. A. Restivo. On codes having no finite completions. Discrete Math., 17:309–316, 1977.

    Article  Google Scholar 

28. R.A. Scholtz. Codes with synchronization capability. IEEE Trans. Inform. Theory, IT-2:135–142, 1966.

    Article  Google Scholar 

29. M.-P. Schützenberger. On a factorization of free monoids. Proc. Amer. Math. Soc., 16:21–24, 1965.

    Google Scholar 

30. M.-P. Schützenberger. Sur une question concernant certains sous-monoïdes libres. C. R. Acad. Sci. Paris, 261:2419–2420, 1965.

    Google Scholar 

31. H.J. Shyr. Free Monoids and Languages. Hon Min Book Company, Taichung, second edition, 1991.

    Google Scholar 

32. G. Viennot. Algèbres de Lie libres et monoïdes libres. PhD thesis, University Paris 7, 1974.

    Google Scholar 

33. L. Zhang and Z. Shen. Completion of recognizable bifix codes. Theoret. Comput. Sci., 145:345–355, 1995.

    Article  Google Scholar 

Download references