A quantum circuit model encodes finite automaton transitions in superposition and uses Grover search to find resetting input sequences with quadratic speedup over classical brute-force.
Generating Shortest Synchronizing Sequences using Answer Set Programming
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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
fields
quant-ph 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A quantum model for synchronizing finite state transition systems
A quantum circuit model encodes finite automaton transitions in superposition and uses Grover search to find resetting input sequences with quadratic speedup over classical brute-force.