On the connection of special binary relations with conditions of commuting languages. Part I. Divisors in the global supermonoid

Boris Melnikov

Abstract


The paper discusses various statements describing the connection of special binary relations (exactly, the binary relations of coverage and equivalence in infinity studied in our previous works) with the conditions of commuting languages. Generalizing, we are considering simply formulated properties associated with the use of the product operation (concatenation) of formal languages, not necessarily (but usually) finite languages. Among these problems, is the study of the conditions of equality of degrees of two languages. It is proved, for example, that in the case of prefix languages, such equality is equivalent to the presence of a common root of the considered sets, defined for the concatenation operation in the usual way. At the beginning of the paper, some auxiliary statements are given; they are related to the possible choice of its left divisor for a given language. Further, the obtained results about the left divisor are considered in particular, which are successfully reformulated if the languages considered in the statements can be obtained as a result of the action of any morphisms. Next, we consider the conditions for the presence of a common root in the global supermonoid for some its two elements. After that, we consider various consequences of the condition of possible commutation of two languages: first in the general case, and then in the presence of the prefix condition of the given languages. At the end of the paper, some interesting examples are given, as well as the problems are formulated that have not yet been solved.

Full Text:

PDF (Russian)

References


Melnikov B. Description of special submonoids of the global supermonoid of the free monoid // News of higher educational institutions. Mathematics. – 2004. – No. 3. – P. 46–56 (in Russian).

Skornyakov L. (Ed.) General Algebra. Vol. 2. – Moscow, Nauka. – 1991. – 480 p. (in Russian).

Cohn P. Free rings and their relations. – NY, Academic Press. – 1971. – 334 p.

Melnikov B. Some equivalence problems for free monoids and for subclasses of the CF-grammars class // Number theoretic and algebraic methods in computer science, World Sci. Publ. – 1995. – P. 125–137.

Melnikov B. Subclasses of the context-free languages class (monograph). – Moscow, Moscow State University Ed. – 1995. – 174 p. –

ISBN 5-211-03448-1 (in Russian).

Dubasova O., Melnikov B. On an extension of the class of context-free languages // Programming and Computer Software (Russian Academy of Sciences Ed.). – 1995. – No. 6. – P. 46–54 (in Russian).

Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 441– 454.

Korabelshchikova S., Melnikov B. Maximum prefix codes and subclasses of the context-free languages class // Bulletin of the Northern (Arctic) Federal University. Series: Natural Sciences. – 2015. – No. 1. – P. 121–129 (in Russian).

Korabelshchikova S., Melnikov B. Iterations of languages and maximum prefix codes // Bulletin of the Voronezh State University. Series: Physics. Math. – 2015. – No. 2. – P. 106–120 (in Russian).

Korabelshchikova S., Melnikov B. On the common root of elements of the global supermonoid // Bulletin of Northern (Arctic) Federal University. Series: Natural Sciences. 2016. – No. 3. – P. 91–96. (in Russian)

Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language // International Journal of Open Information Technologies. – 2019. – Vol. 7. No. 3. – P. 1–6.

Melnikov B. 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).

Melnikov B. 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. Semi-lattices of the subsets of potential roots in the problems 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).

Melnikov B., Melnikova A. On the problems of extracting the root from a given finite language // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. ??. – P. ??–?? (in Russian).

Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.

Pin J.-E. Mathematical Foundations of Automata Theory. – Berlin, Springer-Verlag. – 2012. – 310 p.

Melnikov B., Vylitok A., Melnikova E. Iterations of languages and finite automata // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 12. – P. 1–7 (in Russian).

Melnikov B. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian Social State University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7 (in Russian).


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162