Binary Completely Reachable Automata
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Binary Completely Reachable Automata
|
|
| Автор |
Casas, D.
Volkov, M. V. |
|
| Тематика |
CAYLEY DIGRAPH
COMPLETE REACHABILITY DETERMINISTIC FINITE AUTOMATON STRONGLY CONNECTED DIGRAPH TRANSITION MONOID DIRECTED GRAPHS FINITE AUTOMATA CAYLEY DIGRAPH COMPLETE REACHABILITY DETERMINISTIC FINITE AUTOMATA NON-EMPTY SETS POLYNOMIAL-TIME ALGORITHMS REACHABILITY STATE-SETS STRONGLY CONNECTED STRONGLY CONNECTED DIGRAPH TRANSITION MONOID POLYNOMIAL APPROXIMATION |
|
| Описание |
We characterize complete deterministic finite automata with two input letters in which every non-empty set of states occurs as the image of the whole state set under the action of a suitable input word. The characterization leads to a polynomial-time algorithm for recognizing this class of automata. © 2022, Springer Nature Switzerland AG.
Ministry of Education and Science of the Russian Federation, Minobrnauka, (FEUZ-2020-0016) The authors were supported by the Ministry of Science and Higher Education of the Russian Federation, project FEUZ-2020-0016. |
|
| Дата |
2024-04-08T11:06:03Z
2024-04-08T11:06:03Z 2022 |
|
| Тип |
Conference paper
Conference object (info:eu-repo/semantics/conferenceObject) info:eu-repo/semantics/submittedVersion |
|
| Идентификатор |
Casas, D & Volkov, MV 2022, Binary Completely Reachable Automata. в LATIN 2022: Theoretical Informatics: Book Series. Том. 13568 LNCS, Chapter 21, LATIN 2022: Theoretical Informatics, Том. 13568, Springer, стр. 345-358. https://doi.org/10.1007/978-3-031-20624-5_21
Casas, D., & Volkov, M. V. (2022). Binary Completely Reachable Automata. в LATIN 2022: Theoretical Informatics: Book Series (Том 13568 LNCS, стр. 345-358). [Chapter 21] (LATIN 2022: Theoretical Informatics; Том 13568). Springer. https://doi.org/10.1007/978-3-031-20624-5_21 978-303120623-8 0302-9743 Final All Open Access; Green Open Access https://arxiv.org/pdf/2205.09404 https://arxiv.org/pdf/2205.09404 http://elar.urfu.ru/handle/10995/131267 10.1007/978-3-031-20624-5_21 85144573404 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Springer Science and Business Media Deutschland GmbH
|
|
| Источник |
Lecture Notes in Computer Science
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|