Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/101464
Название: | Preimage problems for deterministic finite automata |
Авторы: | Berlinkov, M. V. Ferens, R. Szykuła, M. |
Дата публикации: | 2021 |
Издатель: | Academic Press Inc. |
Библиографическое описание: | Berlinkov M. V. Preimage problems for deterministic finite automata / M. V. Berlinkov, R. Ferens, M. Szykuła. — DOI 10.1016/j.jcss.2020.08.002 // Journal of Computer and System Sciences. — 2021. — Vol. 115. — P. 214-234. |
Аннотация: | Given a subset of states S of a deterministic finite automaton and a word w, the preimage is the subset of all states mapped to a state in S by the action of w. We study three natural problems concerning words giving certain preimages. The first problem is whether, for a given subset, there exists a word extending the subset (giving a larger preimage). The second problem is whether there exists a totally extending word (giving the whole set of states as a preimage)—equivalently, whether there exists an avoiding word for the complementary subset. The third problem is whether there exists a resizing word. We also consider variants where the length of the word is upper bounded, where the size of the given subset is restricted, and where the automaton is strongly connected, synchronizing, or binary. We conclude with a summary of the complexities in all combinations of the cases. © 2020 Elsevier Inc. |
Ключевые слова: | AVOIDING WORD EXTENDING WORD EXTENSIBLE SUBSET RESET WORD SYNCHRONIZING AUTOMATON FINITE AUTOMATA ROBOTS DETERMINISTIC FINITE AUTOMATA PRE IMAGES PRE-IMAGE PROBLEM STRONGLY CONNECTED SET THEORY |
URI: | http://elar.urfu.ru/handle/10995/101464 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Идентификатор РИНЦ: | 45327587 |
Идентификатор SCOPUS: | 85090002869 |
Идентификатор WOS: | 000579172100012 |
Идентификатор PURE: | 13654241 b8eaa0c0-ad57-458b-ba05-33b905ce1edd |
ISSN: | 220000 |
DOI: | 10.1016/j.jcss.2020.08.002 |
Сведения о поддержке: | We thank the anonymous referee for careful reading and detailed comments. This work was supported by the Competitiveness Enhancement Program of Ural Federal University under grant No. 02.A03.21.006 (Mikhail Berlinkov), and by the National Science Centre , Poland under project number 2014/15/B/ST6/00615 (Robert Ferens) and 2017/25/B/ST6/01920 (Marek Szykuła). |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-85090002869.pdf | 737,63 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.