Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we return to the topic related to one important binary relation on the set of formal languages (considered primarily on the set of iterations of nonempty finite languages), i.e. the equivalence relation at infinity. First of all, we consider examples of the application of this relation (both examples of the need for its implementation, and examples of its use) in various fields of the theory of formal languages, discrete mathematics, and abstract algebra. To simplify the consideration of equivalence at infinity we formulate a simpler binary relation over the set of languages, i.e. the covering relation, the double application of which is equivalent to the application of the equivalence relation at infinity. Next, we consider an algorithm for verifying the fulfillment of the coverage relation, and then we define auxiliary objects used both for proving the correctness of this algorithm and for other problems in the theory of formal languages. As one of the comments on the algorithm, we give the corresponding computer program, consider examples of its operation for specific input languages, after that, we formulate the definitions of the objects associated with them, in particular, the definition of infinite trees of the coverage relation. With their help we prove the correctness of the algorithm for checking the fulfillment of the coverage relation, and also estimate the complexity of this algorithm.

Full Text:

PDF (Russian)

References


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

Lallement G. Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p.

Melnikov B. Algorithm for checking the equality of infinite iterations of finite languages // Bulletin of the Moscow University, Series 15 (“Computational Mathematics and Cybernetics”). – 1996. – No. 4. – P. 49–54 (in Russian).

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

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.

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

Dubasova О., Melnikov B. On an extension of the context­free language class // Programming (Russian Academy of Sciences). –

– No. 6. – P. 46–58 (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. The 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)


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162