Publication: On the Algorithm for Checking the Equivalence Condition of Iterations of Finite Languages
Дата
2021
Авторы
Melnikov, B.
Melnikova, A.
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.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 non-empty finite languages). This is the “equivalence relation at infinity”. Before, 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 formal language theory, discrete mathematics, and abstract algebra. To simplify the consideration of equivalence at infinity, we formulate a simpler binary relation in a 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 the algorithm for checking the fulfillment of the coverage relation, and then we define auxiliary objects used both to prove the correctness of this algorithm and for other problems of the theory of formal languages. As one of the comments on the algorithm, we checked all the results with the help of special computer programs. We consider examples of its operation for some input languages, and then formulate definitions of related objects, 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. #CSOC1120
Описание
Ключевые слова
Цитирование
Melnikov, B. On the Algorithm for Checking the Equivalence Condition of Iterations of Finite Languages / Melnikov, B., Melnikova, A. // Lecture Notes in Networks and Systems. - 2021. - 228. - P. 365-373. - 10.1007/978-3-030-77448-6_34