Efficient Divide-and-Conquer Simulations Of Symmetric FSAs
David Pritchard · 2007
A finite-state automaton (FSA) is an abstract machine with finite working memory, whose input is a string from a finite alphabet, which reads the input one character at a time, and which has a deterministic transition function. An FSA is symmetric if its output is independent of the order in which the input symbols are read, i.e., if the output is invariant under permutations of the input. We show that, given a symmetric FSA A, there is a deterministic divide-and-conquer process that simulates A whose intermediate results are no larger than the size of A’s memory. In comparison, for a general (not necessarily symmetric) FSA, a similar divide-and-conquer implementation has long been known via functional composition but entails an exponential increase in the size of the state space. Our result has applications to parallel processing and to symmetric FSA networks. The first step in the construction is to remove some redundancy in the states of the FSA. The second step is that, assuming the FSA is irredundant, to show that the black-box property of being symmetric implies a more “transparent ” property: namely, the transition operators of the FSA commute. Following the proof of this result we give the simple construction and discuss possible extensions. 1