×

On coding morphisms for zigzag codes. (English) Zbl 0766.68074

Summary: We are dealing with the zigzag codes in connection with monoid morphisms and free group morphisms. The injectivity of free group morphisms plays here the role of that of free monoid morphisms for ordinary codes. Subsets of free group words describing behaviours of zigzag factorizations allows us to characterize zigzag codes in different ways. Every two-element code is a zigzag code. The free monoid morphisms preserving the property of being a zigzag code are exactly the coding morphisms for the biprefix codes.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. M. ANSELMO, Automates et codes zigzag, R.A.I.R.O. Inform. Theor. Appl., 1991, 25, 1, pp. 49-66. Zbl0735.68050 MR1104411 · Zbl 0735.68050
[2] 2. M. ANSELMO, Sur les codes zigzag et leur décidabilité, Theoret. Comput. Sci., 1990, 74, pp. 341-354. Zbl0701.68057 MR1073770 · Zbl 0701.68057 · doi:10.1016/0304-3975(90)90083-T
[3] 3. M. ANSELMO, Automates bilatères et codes zigzag Thèse L.I.T.P., 1990, n^\circ 90-27.
[4] 4. J. BERSTEL, Transductions and Context Free Languages, Teubner Studienbucher, Stuggart, 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[5] 5. J. BERSTEL and D. PERRIN, Theory of Codes, Academic Press, New York, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[6] 6. J. C. BIRGET, Two Way Automaton Computations, R.A.I.R.O. Inform. Theor. Appl., 1990, 24, 1, pp. 47-66. Zbl0701.68058 MR1060466 · Zbl 0701.68058
[7] 7. DO LONG VAN, B. LE SAËC and I. LITOVSKY, Stability for the Zigzag Submonoids, Rapp. interne LaBRI No. 91-37, Bordeaux, 1991, Theoret. Comput Sci. (to appear). Zbl0782.68069 MR1202019 · Zbl 0782.68069 · doi:10.1016/0304-3975(93)90192-V
[8] 8. M. MADONIA, S. SALEMI and T. SPORTELLI, On Z-Submonoids and Z-Codes, R.A.I.R.O. Inform. Theor. Appl., 1991, 25, 4, pp. 305-322. Zbl0764.68089 MR1134385 · Zbl 0764.68089
[9] 9. M. MADONIA, S. SALEMI and T. SPORTELLI, A Generalization of Sardinas, Patterson’s Algorithm to Z-Codes, Theoret. Comput. Sci. (to appear). Zbl0778.68052 MR1202020 · Zbl 0778.68052 · doi:10.1016/0304-3975(93)90193-W
[10] 10. J. P. PÉCUCHET, Automates Boustrophédons semigroupes de Birget et monoïde inversif libre, R.A.I.R.O. Inform. Theor. Appl., 1985, 19, 1, pp.71-100. Zbl0604.68094 MR795773 · Zbl 0604.68094
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.