2019/03/25 by Hanan Shabana, Mikhail V. Volkov, Shabana, Hanan +1 · 2 citations
Computer Science · #68Q45 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #msc:68Q45
paper · pdf · doi:10.48550/arxiv.1903.10549
15 pages, 3 figures
arxiv created 2019/03/25 · arxiv updated 2019/03/27
We approach the task of computing a carefully synchronizing word of minimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experimental results demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used.