Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: 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.pdf195,74 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.