## 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

### MSC:

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

### Keywords:

morphism; L-code; cryptography; number systems
Full Text:

### References:

  Kahn, D., The Codebreakers (1967), MacMillan: MacMillan New York  Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025  Rozenberg, G.; Salomaa, A., The Mathematical Theory of L System (1980), Academic Press: Academic Press New York · Zbl 0365.68072  Ryska, N.; Herda, S., Kryptographische Verfahren in der Datenverarbeitung (1980), Springer: Springer Berlin · Zbl 0426.68107  Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025  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.