On Decomposition of Maximal Prefix Codes

Authors: Nikolai Krainiukov, Boris Melnikov

Abstract:

We study the properties of maximal prefix codes. The codes have many applications in computer science, theory of formal languages, data processing and data classification. Our approaches to study use finite state automata (so-called flower automata) for the representation of prefix codes. An important task is the decomposition of prefix codes into prime prefix codes (factors). We discuss properties of such prefix code decompositions. A linear time algorithm is designed to find the prime decomposition. We used the GAP computer algebra system, which allows us to perform algebraic operations for free semigroups, monoids and automata.

Keywords: Maximal prefix code, regular languages, flower automata, prefix code decomposing.

References:

[1] G. Lallement Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p
[2] J. Berstel, D. Perrin, Theory of Codes, Academic Press, New York, 1985.
[3] W. Brauer. Introduction in the Finite Automata Theory. Moscow: Radio I Svyaz Publ., 1987, 390 p. (in Russian).
[4] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002
[5] B. Melnikov. Regular languages and nondeterministic finite automata. Moscow: RGSU Publ., 2018. 179 p. (in Russian).
[6] B.F. Melnikov, A. A. Melnikova 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).
[7] V. Dolgov, B. Melnikov, A. Melnikova. “The loops of the basis finite automaton and the connected questions.” Bulletin of the Voronezh State University. Series: Physics. Mathematics, no. 4, pp. 95–111, 2016 (in Russian).
[8] A. Mateescu, A. Salomaa, S. Yu, On the decomposition of finite languages. Technical Report 222, Turku Centre for Computer Science (1998).
[9] Mateescu, A., Salomaa, A., S. Yu, (2002). Factorizations of languages and commutativity conditions. Acta Cybernetica, 15(3), 339-351.
[10] B.F. Melnikov. 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).
[11] B.F. Melnikov Semi-lattices of the subsets of potential roots in theproblems of the formal languages theory. Part II. Constructing an inverse morphism International Journal of Open Information Technologies. 2022. Vol. 10. No 5. P. 1–8 (in Russian).
[12] B.F. Melnikov 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), pp. 8–16.
[13] V.V. Dang, N.L. Dodonova, S. Yu. Korabelshchikova, B.F. Melnikov 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).