Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/259570
Заглавие документа: | Subset synchronization in monotonic automata |
Авторы: | Ryzhikov, A. Shemyakov, A. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика |
Дата публикации: | 2018 |
Издатель: | IOS Press |
Библиографическое описание источника: | Fundam Inf 2018;162(2-3):205-221. |
Аннотация: | We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing. |
URI документа: | https://elib.bsu.by/handle/123456789/259570 |
DOI документа: | 10.3233/FI-2018-1721 |
Scopus идентификатор документа: | 85051948721 |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
1703.06356.pdf | 216,69 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.