Synchronizing Heuristics for Non-strongly Connected Automata

Term: 
2016-2017 Summer
Faculty Department of Project Supervisor: 
Faculty of Engineering and Natural Sciences
Number of Students: 
1
PDF icon 2._odol-berk_airiuci-synchronizing_heuristics_for_non-strongly_connected_automata-final-revised.pdf

ABSTRACT

  • Finding a shortest synchronizing sequence is an NP-Hard problem (Eppstein, 1990). There are heuristics (Eppstein, 1990; Roman and Szykula, 2015) to find a short synchronizing sequence.
  • Some heuristics work fast but produce longer synchronizing sequences and some work slow but produce shorter synchronizing sequences. •
  • We propose a method for using these heuristics taking into account the connectedness of automata to make the heuristics work faster than their original versions, without sacrificing the quality of the synchronizing sequences.

OBJECTIVES
Using synchronizing heuristics with our method to make the heuristics work faster than their original versions, without sacrificing the quality of the synchronizing sequences.