Two Tests for the Linearity of Sequential Machines
Juris Hartmanis · IEEE Transactions on Electronic Computers · 1965
This paper describes two tests for the existence of a linear state assignment for binary input sequential machines. The first test is based on ``transfer sequences'' which map one stationary state of a machine onto another stationary state. It is shown that from a minimal transfer sequence of a machine one can read off directly a linear assignment of this machine if one exists. The second test uses ``ignorance'' computations by means of partitions and previously developed results about sequential machine structure.