  Finite state automata (FSA) are ubiquitous in computer science. Two of the
most important algorithms for FSA processing are the conversion of a
non-deterministic finite automaton (NFA) to a deterministic finite automaton
(DFA), and then the production of the unique minimal DFA for the original NFA.
We exhibit a parallel disk-based algorithm that uses a cluster of 29 commodity
computers to produce an intermediate DFA with almost two billion states and
then continues by producing the corresponding unique minimal DFA with less than
800,000 states. The largest previous such computation in the literature was
carried out on a 512-processor CM-5 supercomputer in 1996. That computation
produced an intermediate DFA with 525,000 states and an unreported number of
states for the corresponding minimal DFA. The work is used to provide strong
experimental evidence satisfying a conjecture on a series of token passing
networks. The conjecture concerns stack sortable permutations for a finite
stack and a 3-buffer. The origins of this problem lie in the work on restricted
permutations begun by Knuth and Tarjan in the late 1960s. The parallel
disk-based computation is also compared with both a single-threaded and
multi-threaded RAM-based implementation using a 16-core 128 GB large shared
memory computer.
