L codes and number systems. (English) Zbl 0531.68027

Given a morphism \(h: V^*\to V^*\) (\(V\) is an alphabet), the authors define a mapping \(h: V^*\to V^*\), by putting: \(\bar h(v_ 1\cdots v_ n)=h(v_ 1)h^ 2(v_ 2)\cdots h^ n(v_ n)\), \(\bar h(\Lambda)=\Lambda\). Now, \(h\) is called an L-code (resp. almost L-code) if \(\bar h(a)=\bar h(b)\) entails \(a=b\), for all \(a,b\in V^*\) (resp. for all \(a,b\in V^*\), such that \(| a| \neq t\) and \(| b| \neq t\), where \(t\) is a positive integer depending on \(h\)). As every code, i.e. injective morphism, is also an L-code (theorem 1), the concept of L-code appears to be a natural generalization of that of code. The authors give a nice characterization of L-codes in terms of so-called number systems, which allows to establish several fundamental properties of L-codes. The main attention is focused on unary L-codes, i.e. such \(h\) that \(h(v)=v^ n\) for \(v\in V\) \((n\) depends on \(v)\), and the central result (theorem 5) is: every morphism \(h\), such that \(h(v)=v^ n\), \(h(v')=v^ r\) \((v=\{v,v'\})\), \(n\geq 2\), \(r\geq 1\), \(r\neq n\), is either an L-code or an almost L-code. This fails to hold true for the three-element \(v\), and to find analogous theorems for greater alphabets has been left an open problem.
The paper contains a number of closely related results. As the unary morphisms are usually non-codes, the afore-mentioned theorem shows indeed that the author’s new concept is a powerful one. The authors indicate cryptography as a possible domain of applications.
Reviewer: W. Buszkowski


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


[1] Kahn, D., The Codebreakers (1967), MacMillan: MacMillan New York
[2] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[3] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L System (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[4] Ryska, N.; Herda, S., Kryptographische Verfahren in der Datenverarbeitung (1980), Springer: Springer Berlin · Zbl 0426.68107
[5] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[6] Salomaa, A., Jewels of Formal Language Theory (1981), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0487.68063
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.