Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks

Details Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks

2011-03-29

arxiv.org/abs/1103.5736v1

Computer Science

Distributed, Parallel, and Cluster Computing

14 pages, 4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-164405