2013/12/20 by Canan Güniçen, Güniçen, Canan, Esra Erdem +3
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.AI
paper · pdf · doi:10.48550/arxiv.1312.6146
Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 6th International Workshop, August 25, 2013, Istanbul, Turkey
arxiv created 2013/12/20 · openalex publication_date 2013/12/20 · arxiv updated 2013/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a finite state automaton, a synchronizing sequence is an input sequence that takes all the states to the same state. Checking the existence of a synchronizing sequence and finding a synchronizing sequence, if one exists, can be performed in polynomial time. However, the problem of finding a shortest synchronizing sequence is known to be NP-hard. In this work, the usefulness of Answer Set Programming to solve this optimization problem is investigated, in comparison with brute-force algorithms and SAT-based approaches. Keywords: finite automata, shortest synchronizing sequence, ASP