Experimental study of the shortest reset word of random automata
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Experimental study of the shortest reset word of random automata
|
|
| Автор |
Skvortsov, E.
Tipikin, E. |
|
| Тематика |
EXPERIMENTAL STUDIES
HIGH PROBABILITY RESET WORDS SAT SOLVERS SUBLINEAR SYNCHRONIZING AUTOMATA AUTOMATA THEORY |
|
| Описание |
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.
|
|
| Дата |
2024-04-24T12:38:26Z
2024-04-24T12:38:26Z 2011 |
|
| Тип |
book-chapter
Other (info:eu-repo/semantics/other) info:eu-repo/submittedVersion |
|
| Идентификатор |
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
978-3-64222255-9 0302-9743 Final All Open Access, Green https://arxiv.org/pdf/1105.1704.pdf http://elar.urfu.ru/handle/10995/132596 10.1007/978-3-642-22256-6_27 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Springer Berlin Heidelberg
|
|
| Источник |
Lecture Notes in Computer Science
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|