Return to Answer

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. The TiVo, or any remote, uses an alphabet size of at least as many buttons as there are on the remote control. However, a little hunting on wikipedia shows that "Synchronizing Word" is where "reset sequence" leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the "reset sequence" for a Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upped bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. The TiVo, or any remote, uses an alphabet size of at least as many buttons as there are on the remote control. However, a little hunting on wikipedia shows that "Synchronizing Word" is where "reset sequence" leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the "reset sequence" for a Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upper bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. However, a little hunt on wikipedia shows that "Synchronizing Word" is where "reset sequence leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the "reset sequence" for a Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upped bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. The TiVo, or any remote, uses an alphabet size of at least as many buttons as there are on the remote control. However, a little hunting on wikipedia shows that "Synchronizing Word" is where "reset sequence" leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the "reset sequence" for a Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upped bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. However, a little hunt on wikipedia shows that "Synchronizing Word" is where "reset sequence leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upped bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.

I've played with this problem in real life with a TiVo, wanting it to go to sleep (a low power consumption state) without having to turn on the monitor to watch as its states changed. However, a little hunt on wikipedia shows that "Synchronizing Word" is where "reset sequence leads to.

For $n$-state DFAs over a $k$-letter input alphabet in which all state transitions preserve the cyclic order of the states, an algorithm by David Eppstein finds a synchronizing word in $O(n^3+kn^2)$ time and $O(n^2)$ space. The name of that paper is "Reset Sequences for Monotonic Automata" .

Finding and estimating the length of the "reset sequence" for a Deterministic Finite Automaton has been studied since the 1960's. The Černý conjecture posits $(n-1)^2$ as the upped bound of for the length of the shortest synchronizing word, for any $n$-state complete DFA (a DFA with complete state transition graph).

The way you've posed your question sets $k=2$, since the transitions can only be labeled by the two buttons as input, thus the Deterministic Finite Automaton underlying your question will have a directed graph with at most two outbound arcs at each state.