For a synchronizing automaton, there can be multiple synchronizing sequences. Considering the practical applications of automata and synchronizing sequences (such as resetting a digital circuit which does not have a reset input, regaining the control of a discrete event system whose current state information is missing, etc), shortest possible synchronizing sequences are of interest. However, finding shortest synchronizing sequences is a hard problem.
For this reason, there are heuristic algorithms to find (not the shortest but) short synchronizing sequences.
In this project we will consider some improvements on the existing synchronizing heuristics for special classes of automata and if possible, we will suggest new heuristics.
We already have an implementation of the existing heuristics. You will need to implement the new heuristics (which would be easy to do based on the existing code). In addition, you will either use a library or implement code for some basic graph algorithms. You will perform experiments using these implementations.
The project requires programming. Therefore you should have taken CS201/CS204, at least. Although not necessary, having taken courses like CS300, CS301, CS302 is a plus.
.jpg)