Is there a reset sequence? - MathOverflow

Is there a reset sequence?

2010-09-12T02:37:59Z

There is a question someone (I'm hazy as to who) told me years ago. I found it fascinating for a time, but then I forgot about it, and I'm out of touch with any subsequent developments. Can anyone better identify the problem or fill in the history, and say whether it's still unsolved? It's a challenging question if I've gotten it right. Here it is:

Suppose you have some kind of machine with two buttons, evidently designed by people with poor instinct for UI. The machine has many states in which the buttons do different things. Here are the assumptions:

There is no periodic quotient of the state space: no way to label states by an n-cycle so that both buttons advance the label by 1 mod n.
It is not reversible: there are situations when two states merge into one.
It's ergodic: you can get from any state to any other state by some sequence of buttons.

Now suppose its dinky little LCD is faded or broken, so you can't actually tell what the state it's in. Is there necessarily a universal reset code, a sequence that will get you to a known state no matter where you start? (Formally, this is a finite state automaton, or an action of the free 2-generator semigroup on a finite set, and asks whether some element acts as a constant map).

Answer by S. Carnahan for Is there a reset sequence?

2010-09-12T03:17:22Z

I believe you are referring to the Road coloring theorem. It was solved in this preprint.

Answer by sleepless in beantown for Is there a reset sequence?

2010-09-12T03:26:05Z

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.

Answer by umar for Is there a reset sequence?

2010-09-12T03:56:41Z

I think this paper by Rob Schapire and Ron Rivest on "homing sequences" in deterministic finite state automata might contain the answer to your question. From the paper:

"Informally, a homing sequence is a sequence of inputs that, when fed to the machine, is guaranteed to 'orient' the learner: the outputs produced in executing the homing sequence completely determine the state reached by the automaton at the end of the homing sequence ... Every finite-state machine has a homing sequence."

Admittedly, I haven't read the paper carefully enough to be sure that the problem it studies exactly matches your formulation, but at a high-level it seems closely related.