wpt@princeton.UUCP (William Thurston) (11/20/86)
Here is another problem, which I learned from Roy Adler,
a mathematician at IBM, Yorktown Heights:
A finite state automaton F is a finite directed graph with the outgoing edges
from each vertex labeled (in 1-1 correspondence with) the elements of a finite
set A (called the alphabet). From any vertex v of F, the paths starting from
v are in 1-1 correspondence with words in A*, that is, sequences of elements of
A. A reset code for F is a word R in A* such that, no matter where you start,
you end up at the same vertex w after following the instructions R.
Some finite state automata have reset codes, others do not. For example,
if the incoming edges at each vertex are also in 1-1 correspondence with
A, elements of A act as permutations on the vertices, so there is no reset
code.
The question: Suppose that G is a finite directed graph (unlabeled) with
two outgoing edges from each vertex, having the property that for any pair of
vertices there are paths of equal length beginning at the two vertices and
ending at a common vertex. Does there exist a labeling of the edges of G
by A={red, blue} so the resulting finite state automaton admits a
reset code?
(Aside.
The set of modes of many editors, laser printers, etc, describe a finite
state machine. I spent several hours once constructing a reset code for
our laserprinter, that works at least most of the time.
In the editor vi, a single <esc> usually resets,
but you might need <esc><esc> in case you were at the state
default -> :^V. The sequence <esc><esc><cr>:vi<cr> does a little better,
in case you are at state default->Q , but it doesn't take care of the state
default -> Q:a<cr>stuff. I don't no offhand
a reset code which I'm confident could not to have a possible destructive
effect on the text being edited. Perhaps <esc><esc>Qa<cr>.vi<cr> does pretty
well, but it's hard to be sure. This is not counting the modes such as
default ->:se ai noshowmatch<cr>. )
Bill Thurston Mathematics Department, Princeton University princeton!wpt