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.95 n 0.55.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ananichev, D.S., Gusev, V.V., Volkov, M.V.: Slowly synchronizing automata and digraphs. In: Hlinený and Kucera [13], pp. 55–65
Ananichev, D.S., Volkov, M.V., Zaks, Y.I.: Synchronizing automata with a letter of deficiency. Theor. Comput. Sci. 376(1-2), 30–41 (2007)
Berlinkov, M.V.: Approximating the Minimum Length of Synchronizing Words Is Hard. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 37–47. Springer, Heidelberg (2010)
Bulatov, A.A., Skvortsov, E.S.: Phase transition for local search on planted SAT. CoRR, abs/0811.2546 (2008)
černy, J.: Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikalny Časopis Slovensk. Akad. Vied 14, 208–216 (1964)
Cook, S.A.: The complexity of theorem-proving procedures. In: STOC, pp. 151–158 (1971)
Dantsin, E., Hirsch, E.A., Wolpert, A.: Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 60–68. Springer, Heidelberg (2006)
Eén, N., Biere, A.: Effective Preprocessing in SAT Through Variable and Clause Elimination. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 61–75. Springer, Heidelberg (2005)
Eén, N., Sörensson, N.: An Extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)
Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19, 500–510 (1990)
Higgins, P.: The range order of a product of i transformations from a finite full transformation semigroup. Semigroup Forum 37, 31–36 (1988), doi:10.1007/BF02573120
Hirsch, E.A.: Sat local search algorithms: Worst-case study. J. Autom. Reasoning 24(1/2), 127–143 (2000)
Hliněný, P., Kučera, A. (eds.): MFCS 2010. LNCS, vol. 6281. Springer, Heidelberg (2010)
Olschewski, J., Ummels, M.: The complexity of finding reset words in finite automata. In: Hlinený and Kucera [13], pp. 568–579
Pin, J.-E.: On two combinatorial problems arising from automata theory. In: Berge, C., Bresson, D., Camion, P., Maurras, J.F., Sterboul, F. (eds.) Proceedings of the International Colloquium on Graph Theory and Combinatorics, Combinatorial Mathematics, vol. 75, pp. 535–548. North-Holland, Amsterdam (1983)
Roman, A.: Genetic Algorithm for Synchronization. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 684–695. Springer, Heidelberg (2009)
Evgeny Skvortsov. Google profile, http://profiles.google.com/u/0/108501114510819324139/about
Skvortsov, E.S., Zaks, Y.: Synchronizing random automata. Discrete Mathematics & Theoretical Computer Science 12(4), 95–108 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Skvortsov, E., Tipikin, E. (2011). Experimental Study of the Shortest Reset Word of Random Automata. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, JM., Maurel, D. (eds) Implementation and Application of Automata. CIAA 2011. Lecture Notes in Computer Science, vol 6807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22256-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-22256-6_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22255-9
Online ISBN: 978-3-642-22256-6
eBook Packages: Computer ScienceComputer Science (R0)