Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111366
Название: | Experimental Study of the Shortest Reset Word of Random Automata |
Авторы: | Skvortsov, E. Tipikin, E. |
Дата публикации: | 2011 |
Издатель: | Springer Berlin Heidelberg |
Библиографическое описание: | Skvortsov E. Experimental Study of the Shortest Reset Word of Random Automata / E. Skvortsov, E. Tipikin. — DOI 10.17223/19986645/70/18 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2011. — Vol. 6807 LNCS. — P. 290-298. |
Аннотация: | 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/111366 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Конференция/семинар: | 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: | 9783642222559 |
DOI: | 10.17223/19986645/70/18 |
Сведения о поддержке: | We are grateful to Prof. M.V. Volkov for numerous productive discussions on the topic, and to the anonymous reviewers for their remarks which have helped us make the article more accurate and clear. |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-79961191375.pdf | 195,74 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.