Bounded delay L codes. (English) Zbl 0735.68051

A code is a morphism \(h\). The code obtained by applying \(h\) to the first letter of the plaintext, \(h^ 2\) to the second letter, \(h^ 3\) to the third letter, and so on, is referred to as \(L\)-code. A code being of bounded delay means the existence of a constant \(k\) such that the first \(k\) letters of the cryptotext uniquely determine the first letter of the plaintext. Three notions of bounded \(L\) codes are investigated, their relations with ordinary codes are established.
Reviewer: G.Jumarie


68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
94A60 Cryptography
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[2] Culik, K.; Salomaa, A., Ambiguity and decision problems concerning number systems, Inform. and control, 56, 139-153, (1983) · Zbl 0541.03006
[3] Van, Do Long; Lam, Nguyen Huong; Huy, Phan Trung, On codes concerning bi-infinite words, (1990), Manuscript · Zbl 0816.94012
[4] Frougny, C., Linear numeration systems of order two, Inform. and comput., 77, 233-259, (1988) · Zbl 0648.68066
[5] Honkala, J., Unique representation in number systems and L codes, Discrete appl. math., 4, 229-232, (1982) · Zbl 0537.94024
[6] Honkala, J., Bases and ambiguity in number systems, Theoret. comput. sci., 31, 61-71, (1984) · Zbl 0546.68066
[7] Honkala, J., It is decidable whether or not a permutation-free morphism is an L code, Internat. J. comput. math., 22, 1-11, (1987) · Zbl 0684.68091
[8] Maurer, H.; Salomaa, A.; Wood, D., L codes and number systems, Theoret. comput. sci., 22, 331-346, (1983) · Zbl 0531.68027
[9] Salomaa, A, Jewels of formal language theory, (1981), Computer Science Press Rockville, MD · Zbl 0487.68063
[10] Salomaa, A., Public-key cryptography, (1991), Springer Berlin · Zbl 0712.68003
[11] A. Salomaa, Cryptographic properties of L codes, in preparation.
[12] Salomaa, A., L codes: variations on a theme of MSW, Ten years IIG, report 260, 218, (1988)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.