L codes and number systems. (English) Zbl 0531.68027

Maurer, H. A.; Salomaa, A.; Wood, D.

Theor. Comput. Sci. 22, 331-346 (1983).

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

References:

[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