Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/132596
Название: | Experimental study of the shortest reset word of random automata |
Авторы: | Skvortsov, E. Tipikin, E. |
Дата публикации: | 2011 |
Издатель: | Springer Berlin Heidelberg |
Библиографическое описание: | Skvortsov, E., & Tipikin, E. (2011). Experimental study of the shortest reset word of random automata. In Lecture Notes in Computer Science. Implementation and Application of Automata (pp. 290–298). doi:10.1007/978-3-642-22256-6_27 |
Аннотация: | In this paper we describe an approach to finding the shortest reset word of a finite synchronizing automaton by using a SAT solver. We use this approach to perform an experimental study of the length of the shortest reset word of a finite synchronizing automaton. The largest automata we considered had 100 states. The results of the experiments allow us to formulate a hypothesis that the length of the shortest reset word of a random finite automaton with n states and 2 input letters with high probability is sublinear with respect to n and can be estimated as 1.95n0.55. © 2011 Springer-Verlag. |
Ключевые слова: | EXPERIMENTAL STUDIES HIGH PROBABILITY RESET WORDS SAT SOLVERS SUBLINEAR SYNCHRONIZING AUTOMATA AUTOMATA THEORY |
URI: | http://elar.urfu.ru/handle/10995/132596 |
Условия доступа: | info:eu-repo/semantics/openAccess All Open Access, Green |
Конференция/семинар: | 16th International Conference on Implementation and Application of Automata, CIAA 2011 |
Дата конференции/семинара: | 13 July 2011 through 16 July 2011 |
Идентификатор SCOPUS: | 79961191375 |
Идентификатор PURE: | 38014697 |
ISSN: | 0302-9743 |
ISBN: | 978-3-64222255-9 |
DOI: | 10.1007/978-3-642-22256-6_27 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-79961191375.pdf | 195,74 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.