Publication: A Polynomial Algorithm for Construction an Automaton for Checking the Equality of Infinite Iterations of Two Finite Languages
Дата
2022
Авторы
Melnikov, B.
Melnikova, A.
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
Purpose: In this paper, we continue the topic related to the special binary relation in a variety of formal languages, so called equivalence relation at infinity. We formulate a simpler binary relation for languages, the cover relation, whose double application is equivalent to application of the equivalence relation at infinity. After that, we considered the algorithm for checking the fulfillment of the coverage relation, defined auxiliary objects used to prove the correctness of this algorithm. Methods: We have defined a specific such automaton for two given finite languages, i.e. primary automaton, PRI; it is deterministic, defined on sets of words, and each of these sets is a subset of the set of prefixes of the second of the given languages. Then we determine the corresponding to such an automaton several options for special non-deterministic automata, actually describing the construction of a given iterative morphism tree. We introduce a completely different object, the so-called simplified prime automaton, NSPRI, which also describes the construction of an iterative morphism tree, but is defined not on sets of words, but on words. Results: One of investigated objects is the infinite iterative tree. In the considered infinite iterative trees, we combine equivalent states; in fact, in doing so, we obtain a deterministic finite automaton. Conclusion: Thus, we are working with many sets of possible prefixes, which makes the algorithm polynomial impossible. So we are building a non-deterministic automaton, defined simply on the set of possible prefixes. This begs the question: when exactly this automaton gives a positive result. We solve this problem with what we demand so that the resulting non-deterministic automaton would be an analogue of an everywhere defined deterministic automaton. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Описание
Ключевые слова
Цитирование
Melnikov, B. A Polynomial Algorithm for Construction an Automaton for Checking the Equality of Infinite Iterations of Two Finite Languages / Melnikov, B., Melnikova, A. // Lecture Notes in Networks and Systems. - 2022. - 502 LNNS. - P. 521-530. - 10.1007/978-3-031-09076-9_47
URI
https://www.doi.org/10.1007/978-3-031-09076-9_47
https://www.scopus.com/record/display.uri?eid=2-s2.0-85135026048&origin=resultslist
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000893642100047
https://openrepository.mephi.ru/handle/123456789/27405
https://www.scopus.com/record/display.uri?eid=2-s2.0-85135026048&origin=resultslist
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000893642100047
https://openrepository.mephi.ru/handle/123456789/27405