On verification algorithms for some binary relations on the general supermonoid of a free monoid

Background. The subjects of the study are free semigroups and special binary relations (free semigroup) defined on the global supermonoid of a free monoid. In this paper, we consider some special binary relations in languages (elements of the global supermonid), especially the so-called equivalence relation at infinity, which we considered in previous papers and which is an equivalence relation. We describe algorithms for verifying the fulfillment of these relations for elements of the global supermonoid of a free monoid. We also consider a special order relation on subsets of a set of words that is given by a language that is minimal in this relation among all languages equivalent at infinity to the given one. Material and methods. General methods of analysis and synthesis are used in this work. Special methods of the theory of formal languages, methods for describing algorithms and methods of working with semigroups are also used, in particular, the method of constructing a morphism of a semigroup. Results. The article gives examples of constructing two languages (two elements of a supermonoid) for which the equivalence relation we are considering is satisfied in the supermonoid. The most important result of the paper is a description of the effective algorithm that answers the question whether the iterations of two given finite languages are equivalent at infinity. Algorithms and examples presented in the article are relevant for the application of special variants of the automated transformation of regular grammatical structures and context-free grammars in compiler building automation systems. Conclusions. In many special cases, described by us in previous publications, the analogues of the considered algorithms are polynomial. However, in the general case, the question of the existence of polynomial algorithms that answer the questions posed in the article remains open.