Published January 1, 2018 | Version v1
Conference paper Open

Using Structure of Automata for Faster Synchronizing Heuristics

  • 1. Sabanci Univ, Fac Engn & Nat Sci, Comp Sci & Engn, Istanbul, Turkey

Description

The problem of finding a synchronizing sequence for an automaton is an interesting problem studied widely in the literature. Finding a shortest synchronizing sequence is an NP-Hard problem. Therefore, there are heuristics to find short synchronizing sequences. Some heuristics work fast but produce long synchronizing sequences, whereas some heuristics work slow but produce relatively shorter synchronizing sequences. In this paper we propose a method for using these heuristics by considering the connectedness of automata. Applying the proposed approach of using these heuristics make the heuristics work faster than their original versions, without sacrificing the quality of the synchronizing sequences.

Files

bib-a636975f-82c2-4f8c-b46c-aa6996e9fce5.txt

Files (241 Bytes)

Name Size Download all
md5:3af2e9f447e75643180a4ce0037b2bf8
241 Bytes Preview Download