On the connection of special binary relations with conditions of commuting languages. Part II. The main statements

Boris Melnikov

Abstract


The paper discusses various statements describing the relationship of special binary relations (defined and investigated in some our previous works binary relations of coverage and equivalence at infinity) with the conditions of
commutation of languages. Generalizing, we can say that some simply formulated properties related to the use of the product operation (concatenation) of formal languages are considered; in this case, languages are not necessarily (but usually) finite. Among the problems under consideration 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 in the considered sets, defined for the concatenation operation in the usual way. Some auxiliary statements related to the possible choice of its left divisor for a given language are given. Especially those of the results obtained about the left divisor are considered, which
can be successfully reformulated if the languages considered in the statements can be obtained as a result of the image of some morphisms. The conditions for the presence of a common root in the global supermonoid for some of its two elements are also considered. After that, various consequences of the condition of possible commutation of two languages are considered: first, in the
general case; then, when executing a special hypothesis, which we called the “Zyu hypothesis” and considered in some previous publications; and then, when the prefix condition of the considered languages is met. In the conclusion, some interesting examples are given, as well as the problems that have not yet been solved are formulated. In the proposed part II of the paper, the main results are
considered, starting with the formulation of the conditions for commuting languages for the general (i.e. “non-prefix”) case. 


Full Text:

PDF (Russian)

References


Melnikov B. On the connection of special binary relations with conditions of commuting languages. Part I. Divisors in the global supermonoid // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 7. – P. 21–29. (In Russian.)

Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

Melnikov B. On the complex of problems for the study of the necessary conditions for the equality of infinite iterations of finite languages // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 1. – P. 1–12. (In Russian.)

Brosalina A., Melnikov B. Commutation in global supermonoid of free monoids // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 353–370. (In Russian.)

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. The use of petal finite automata to verify the fulfillment of a special case of the Zyu hypothesis (for a given finite language) // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 3. – P. 1–11. (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.

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

Alekseeva A., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33. (In Russian.)

Melnikova A. The set of maximal prefix codes and the corresponding semigroup // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 8. – P. 3–7. (In Russian.)

Lipski W. Combinatorics for programmers. – Moscow, Mir. – 1988. – 200 p. (In Russian.)

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

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 4. – P. 1–11. (In Russian.)

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 5. – P. 1–11. (In Russian.)

Melnikov B., Meng Lingqian. Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part I // International Journal of Open Information Technologies. – 2023. – Vol. ??. No. ??. – P. ??–??. (In Russian.)


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162