Generating Shortest Synchronizing Sequences using Answer Set Programming
This work addresses a computational complexity challenge in automata theory, but it appears incremental as it focuses on applying an existing programming paradigm (ASP) to a known hard problem without claiming major breakthroughs.
The authors tackled the NP-hard problem of finding the shortest synchronizing sequence for finite state automata by investigating Answer Set Programming (ASP) as a solution method, comparing it to brute-force and SAT-based approaches, though no concrete numerical results were provided.
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