General Results on Tour Lengths in Machines and Digraphs
Takao Asano, Michiro Shibui, Itsuo Takanami · SIAM Journal on Computing · 1976
A tour in a sequential machine is a shortest input sequence taking the machine from some initial state, through all of its remaining states and back again into its initial state. A. K. Dewdney and A. L. Szilard [2] found the best upper bound for tour length for two classes of machines: the class of n-state sequential machines with unrestricted input alphabet and the class of n-state sequential machines with a two-letter input alphabet. We define a strong circulation on a strong digraph D whose volume is equal to the tour length of D. Characterizing the volume of strong circulation, we derive the best upper bound for tour length for n-state sequential machines with an r-letter input alphabet. Putting $r = 2$ or $r = \infty $, we have the same results as those obtained by A. K. Dewdney and A. L. Szilard.