32
$\begingroup$

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:

  1. 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.

  2. It is not reversible: there are situations when two states merge into one.

  3. 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).

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ "there is no quotient map" from what? $\endgroup$
    – user5810
    Commented Sep 12, 2010 at 3:06

3 Answers 3

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ You may be right, which would means I garbled the statement: perhaps the question as I phrased it is trivial. I'll mull it over a bit. $\endgroup$
    – Bill Thurston
    Commented Sep 12, 2010 at 3:23
  • 4
    $\begingroup$ Syncronizing word at en.wikipedia.org/wiki/Synchronizing_word uses the same diagram as the road coloring theorem wikipedia article and has a few references to Černý's 1964 paper and to Eppstein's article for finding reset sequences for monotonic automata. $\endgroup$
    – sleepless in beantown
    Commented Sep 12, 2010 at 3:29
  • 1
    $\begingroup$ Thanks for helping remove some of my mental haze. I now think I heard the problem from Roy Adler. To clarify: the "Road coloring theorem" tells how, under suitable conditions similar to the above, a digraph with out-degree 2 can be labeled with 2 letters so that there exists a reset code. The problem the way I stated it above is more straightforward to solve and has been known longer, as noted by sleepless in beantown. $\endgroup$
    – Bill Thurston
    Commented Sep 12, 2010 at 3:41
  • 2
    $\begingroup$ Yes, it might be best if you gave "sleepless in beantown" the check mark (and the associated 15 points). $\endgroup$
    – S. Carnahan ♦
    Commented Sep 13, 2010 at 1:18
20
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .