UDC

512.5

Authors

Svetlana Korabel’shchikova*, Boris Mel’nikov**
*Northern (Arctic) Federal University named after M.V. Lomonosov (Arkhangelsk, Russian Federation)
**Togliatti Branch of Samara National Research University named after Academician S.P. Korolev (Togliatti, Russian Federation)

Abstract

The paper presents and proves some properties of global supermonoids of free monoids, which, in turn, are also monoids. We prove the conditions of the existance of the left and right divisors in these global supermonoids, which are non-free. On the basis of these properties the paper proves a necessary condition for the equality A^m = Bⁿ for global supermonoids of free monoids, which is available from global supermonoids A and B of the common root (in general in varying degrees). The results are obtained with the proviso that at least one of the languages has a prefix property. The problem of finding the root of the nth degree of the specified language is also considered. It is solved for a special form language consisting of all words in length from t₁ to t₂ (t₁ ≤ t₂) over the alphabet. The criterion for the root existence of the nth degree is a divisibility of t₁ and t₂ by n. The paper demonstrates the necessary and sufficient condition that the special form language is the root of the nth degree of the selected language of the same form; the concepts of trivial and primitive roots and an example explaining these definitions are given. All the examples given in the article are relevant to the applied problems of the theory, in particular – for the constructing of special versions of the automated conversion of regular grammatical structures and context-free grammars in the compiler construction automation systems. In terms of the introduced concepts we formulate a necessary condition that the language of any kind in the alphabet is the root of the nth degree of a given special form language. The issue of the conditional sufficiency remains open.

Keywords

free monoid, global supermonoid, prefix language, root of the elements of supermonoid

References

1. Melnikov B. Some Equivalence Problems for Free Monoids and for Subclasses of the CF-Grammars Class. Number Theoretic and Algebraic Methods in Computer Science, 1995, pp. 67–68. 
2. Mel’nikov B.F. Opisanie spetsial’nykh podmonoidov global’nogo nadmonoida svobodnogo monoida [Description of Special Submonoids of Global Supermonoid of Free Monoid]. Izvestiya vuzov. Matematika [Russian Mathematics], 2004, no. 3(502), pp. 46–56. 
3. Melnikov B. The Equality Condition for Infinite Catenations of Two Sets of Finite Words. Int. J. of Found. of Comp. Sci., 1993, vol. 4, no. 3, pp. 267–274. 
4. Korabel’shchikova S.Yu., Mel’nikov B.F. Iteratsii yazykov i maksimal’nye prefiksnye kody [Languages Iterations and Maximal Prefix Codes]. Vestnik Voronezhskogo gosudarstvennogo universiteta. Ser.: Fizika. Matematika [Proceedings of Voronezh State University. Series: Physics. Mathematics], 2015, no. 2, pp. 106–120. 
5. Salomaa A. Zhemchuzhiny teorii formal’nykh yazykov [Pearls of Formal Language Theory]. Moscow, 1986. 159 p. 
6. Lalleman Zh. Polugruppy i kombinatornye prilozheniya [Semigroups and Combinatorial Applications]. Moscow, 1985. 440 p. 
7. Lidl R., Pil’ts G. Prikladnaya abstraktnaya algebra [Applied Abstract Algebra]. Yekaterinburg, 1997. 764 p. 
8. Korabel’shchikova S.Yu., Chesnokov A.I., Tutygin A.G. O pervoobraznykh kornyakh iz yazykov spetsial’nogo vida [On the Primitive Roots of Special Form Languages]. Diskretnye modeli v teorii upravlyayushchikh sistem: tr. IX Mezhdunar. konf. (Moskva i Podmoskov’e, 20–22 maya 2015 g.) [Discrete Models in the Theory of Control Systems: Proc. 9th Intern. Conf. (Moscow and Moscow Region, May 20–22, 2015)]. Moscow, 2015, pp. 116–118. 
9. Korabel’shchikova S.Yu., Chesnokov A.I. Lunnaya arifmetika v prilozhenii k zadache izvlecheniya korney iz yazykov spetsial’nogo vida [Moon Arithmetic in Application to the Rooting from the Special Form Languages]. Informatizatsiya protsessov formirovaniya otkrytykh sistem na osnove SAPR, ASNI i sistem iskusstvennogo intellekta “Infos-2015”: 8-ya mezhdunar. nauch.-tekhn. konf. (26–27 iyunya 2015 g.) [Informatization of Formation Processes of Open Systems Based on CAD, ARS and Artificial Intelligence Systems “INFOS- 2015”: 8th Int. Sci. Eng. Conf. (26–27 June, 2015)]. Vologda, 2015, pp. 73–77. 
10. Melnikov B.F., Melnikova A.A. Some Properties of the Basis Finite Automaton. Korean Journal of Computational and Applied Mathematics, 2002, vol. 9, no. 1, pp. 135–150. 
11. Mel’nikov B.F., Pivneva S.V., Rogova O.A. Reprezentativnost’ sluchayno sgenerirovannykh nedeterminirovannykh konechnykh avtomatov s tochki zreniya sootvetstvuyushchikh bazisnykh avtomatov [The Representativeness of Stochastic Generated Nondeterministic Finite State Machines in Terms of the Relevant Basic Automata]. Stokhasticheskaya optimizatsiya v informatike, 2010, vol. 6, no. 1-1, pp. 74–82. 
12. Korabel’shchikova S.Yu., Mel’nikov B.F. Maksimal’nye prefiksnye kody i problema ravenstva v raznykh klassakh yazykov [The Maximum Prefix Codes, and the Problem of Equality in Different Classes of Languages]. Problemy teoreticheskoy kibernetiki: materialy XVII Mezhdunar. konf. (Kazan’, 16–20 iyunya 2014 g.) [Problems of Theoretical Cybernetics: Proc. 17th Int. Conf. (Kazan, 16–20 June, 2014)]. Kazan, 2014, pp. 143–146.