Publication:
A Polynomial Algorithm for Construction an Automaton for Checking the Equality of Infinite Iterations of Two Finite Languages

Простая страница элемента
dc.contributor.authorMelnikov, B.
dc.contributor.authorMelnikova, A.
dc.date.accessioned2024-12-25T08:15:38Z
dc.date.available2024-12-25T08:15:38Z
dc.date.issued2022
dc.description.abstractPurpose: 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.
dc.format.extentС. 521-530
dc.identifier.citationMelnikov, 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
dc.identifier.doi10.1007/978-3-031-09076-9_47
dc.identifier.urihttps://www.doi.org/10.1007/978-3-031-09076-9_47
dc.identifier.urihttps://www.scopus.com/record/display.uri?eid=2-s2.0-85135026048&origin=resultslist
dc.identifier.urihttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000893642100047
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/27405
dc.relation.ispartofLecture Notes in Networks and Systems
dc.titleA Polynomial Algorithm for Construction an Automaton for Checking the Equality of Infinite Iterations of Two Finite Languages
dc.typeConference Paper
dspace.entity.typePublication
oaire.citation.volume502 LNNS
relation.isOrgUnitOfPublication9ee05942-b1d9-4513-a450-ef7a8d2894af
relation.isOrgUnitOfPublication.latestForDiscovery9ee05942-b1d9-4513-a450-ef7a8d2894af
Файлы
Коллекции
Публикации