Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111366
Title: Experimental Study of the Shortest Reset Word of Random Automata
Authors: Skvortsov, E.
Tipikin, E.
Issue Date: 2011
Publisher: Springer Berlin Heidelberg
Citation: 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.
Abstract: 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.
Keywords: EXPERIMENTAL STUDIES
HIGH PROBABILITY
RESET WORDS
SAT SOLVERS
SUBLINEAR
SYNCHRONIZING AUTOMATA
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/111366
Access: info:eu-repo/semantics/openAccess
Conference name: 16th International Conference on Implementation and Application of Automata, CIAA 2011
Conference date: 13 July 2011 through 16 July 2011
SCOPUS ID: 79961191375
ISSN: 0302-9743
ISBN: 9783642222559
DOI: 10.17223/19986645/70/18
metadata.dc.description.sponsorship: 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.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-79961191375.pdf195,74 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.