New Algorithms for Finding Short Reset Sequences in Synchronizing Automata

Authors: Adam Roman

Abstract:

Finding synchronizing sequences for the finite automata is a very important problem in many practical applications (part orienters in industry, reset problem in biocomputing theory, network issues etc). Problem of finding the shortest synchronizing sequence is NP-hard, so polynomial algorithms probably can work only as heuristic ones. In this paper we propose two versions of polynomial algorithms which work better than well-known Eppstein-s Greedy and Cycle algorithms.

Keywords: Synchronizing words, reset sequences, Černý Conjecture

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1055877

References:

[1] D. Eppstein, Reset Sequences for Monotonic Automata, SIAM J. Comput. 19(1990), 500-510.
[2] B. K. Natarajan, An algorithmic Approach to the Automated Design of Parts Orienters, Proc. 27th Annual Symp. Foundations of Computer Science, IEEE (1986), 132-142.
[3] B. K. Natarajan, Some paradigms for the automated design of parts feeders, Internat. J. Robotics Research 8(1989) 6, 89-109.
[4] D. S. Ananichev, M. V. Volkov, Synchronizing Monotonic Automata, Lecture Notes in Computer Science, 2710(2003), 111--121.
[5] Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, E. Shapiro, Programmable and autonomous computing machine made of biomolecules, Nature 414(2001).
[6] Y. Benenson, R. Adar, T. Paz-Elizur, L. Livneh, E. Shapiro, DNA molecule provides a computing machine with both data and fuel, Proc. National Acad. Sci. USA 100(2003) 2191-2196.
[7] L. Dubuc, Les automates circulaires et la conjecture de ČernÛ, Inform. Theor. Appl. 32(1998), 21-34.
[8] A. N. Trahtman, The existence of synchronizing word and Cerny Conjecture for some finite automata, Second Haifa Workshop on Graph Theory, Combinatorics and Algorithms, Haifa (2002).
[9] A. Salomaa, Compositions over a Finite Domain: from Completeness to Synchronizable Automata, Turku Centre for Computer Science, Technical Report No 350(2000).