The set of maximal prefix codes and the corresponding semigroup
Abstract
One of the most numerous classes of algebra are semigroups - apparently, due to the fact that the only axiom that must be fulfilled for a semigroup is the axiom of associativity of the operation given on it. In this paper, it is shown that the set of maximal prefix codes is the set of forming the corresponding semigroup with respect to the concatenation operation specified on it. An important issue remains the idea of the structure of the semigroup, which is also discussed in the article.
The article deals with the issues of morphisms of maximal prefix codes. Based on the representation of the maximum prefix codes as a sequence of words in alphabetical order (if the alphabet is ordered), a proposal is formulated on the possibility of putting a sequence of the lengths of its words in accordance with each such code. Some conditions are discussed under which a maximum prefix code will correspond to a sequence of lengths.
The variant of compression of such codes with the use of word lengths is considered, the algorithm is described. As you know, encoding, compression of information is of great importance in practice. An example of the algorithm execution and a drawing for it are given. It also talks about possible directions for the continuation of the development of the subject of the article, the possibilities of studying maximum prefix codes, their properties, structure, invariants, compression capabilities and unambiguity of decoding, restoration of the source code.
Examples of definitions and properties for maximum prefix codes are given.
Full Text:
PDF (Russian)References
Abstract algebra. Vol. 2 / Artamonov V.A., Saliy V.N., Skornyakov L.A. et al. Moscow: Nauka Publ., Phizmatlit, 1991 (in Russian).
Markov A.A., Introduction to coding theory // M.: Nauka, Gl. ed. phys.-mat. lit., 1982. – 192 p. (in Russian).
Melnikov B., Melnikova A. A polynomial algorithm for checking the fulfillment of the condition of the morphic image of the extended maximal prefix code // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 12. – P. 1–9 (in Russian).
Salomaa A. Pearls of the theory of formal languages // Moscow: Mir, 1986 (in Russian).
Lallement G. Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p. (in Russian).
Birkhoff G., Barty T. Modern applied Algebra // Moscow: Mir, 1976. – 400 p. (in Russian).
Zyablitceva L.V., Korabelshchikova S.Yu., Abramyan M. E. Semilat-tice graphs, matrix representations of idempotent semigroups and Waterloo automaton semilattices // International Journal of Open Information Technologies. 2023. Vol. 11. No 7. P. 69–76 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. 2022. Vol. 10. No. 4. P. 1–9 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an in-verse morphism // International Journal of Open Information Tech-nologies. 2022. Vol. 10. No 5. P. 1–8 (in Russian).
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice // International Journal of Open Information Technologies. 2022. Vol. 10. No. 7. P. 1–9 (in Russian).
Dang V.V., Dodonova N.L., Korabelshchikova S.Yu, Melnikov B.F. SH-weak duality of semigroups and minimum semigroup of SH-approximation // University proceedings. Volga region. Physical and mathematical sciences. 2019. No. 1 (49). P. 29–39 (in Russian).
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162