English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Finite state automata (FSA) are ubiquitous in computer science. Two of themost important algorithms for FSA processing are the conversion of anon-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 commoditycomputers to produce an intermediate DFA with almost two billion states andthen continues by producing the corresponding unique minimal DFA with less than800,000 states. The largest previous such computation in the literature wascarried out on a 512-processor CM-5 supercomputer in 1996. That computationproduced an intermediate DFA with 525,000 states and an unreported number ofstates for the corresponding minimal DFA. The work is used to provide strongexperimental evidence satisfying a conjecture on a series of token passingnetworks. The conjecture concerns stack sortable permutations for a finitestack and a 3-buffer. The origins of this problem lie in the work on restrictedpermutations begun by Knuth and Tarjan in the late 1960s. The paralleldisk-based computation is also compared with both a single-threaded andmulti-threaded RAM-based implementation using a 16-core 128 GB large sharedmemory computer.

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