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.
Obtaining a minimal canonical DFA equivalent to a given NFA is important for the analysis of the classes of permutations generated by token passing in graphs. Such a graph is called a token passing network (TPN) @cite_9 @cite_3 . This is related to the subject permutations @cite_15 , with origins in the 1969 work of Knuth [Section 2.2.1] Knuth:1969 and the 1972 work of Tarjan @cite_23 . TPNs are used to model or approximate a range of data structures, including combinations of stacks, and provide tools for analyzing the classes of permutations that can be sorted or generated using them. Stack sorting problems have been the subject of extensive research @cite_35 . Sorting with two ordered stacks in series is detailed in @cite_36 . Permutation classes defined by TPNs are described in @cite_33 . Very recent work focused on permutations generated by stacks and dequeues @cite_21 . A collection of results on permutation problems expressed as token passing networks is in @cite_0 .
@cite_35 @cite_33 @cite_36 @cite_9 @cite_21 @cite_3 @cite_0 @cite_23 @cite_15
2102928439 2099673747 2068458438 2077632363 2103793661 2017788080
We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for the study of permutation patterns. We also show that they have connections to other areas in combinatorics such as Young tableau, planar graph theory, and simplicial complexes. The study of pattern classes is the study of the involvement order on finite permutations. This order can be traced back to the work of Knuth. In recent years the area has attracted the attention of many combinatoralists and there have been many structural and enumerative developments. We consider permutations classes defined in three different ways and demonstrate that asking the same fixed questions in each case motivates a different view of involvement. Token passing networks encourage us to consider permutations as sequences of integers; grid classes encourage us to consider them as point sets; picture classes, which are developed for the first time in this thesis, encourage a purely geometrical approach. As we journey through each area we present several new results. We begin by studying the basic definitions of a permutation. This is followed by a discussion of the questions one would wish to ask of permutation classes. We concentrate on four particular areas: partial well order, finite basis, atomicity and enumeration. Our third chapter asks these questions of token passing networks; we also develop the concept of completeness and show that it is decidable whether or not a particular network is complete. Next we move onto grid classes, our analysis using generic sets yields an algorithm for determining when a grid class is atomic; we also present a new and elegant proof which demonstrates that certain grid classes are partially well ordered. The final chapter comprises the development and analysis of picture classes. We completely classify and enumerate those permutations which can be drawn from a circle, those which can be drawn from an X and those which The permutations that can be sorted by two stacks in series are considered, subject to the condition that each stack remains ordered. A forbidden characterisation of such permutations is obtained and the number of permutations of each length is determined by a generating function. Lower and upper bounds are given for the the number of permutations of length n generated by two stacks in series, two stacks in parallel, and a general deque. Abstract A transportation graph is a directed graph with a designated input node and a designated output node. Initially, the input node contains an ordered set of tokens 1,2,3, … The tokens are removed from the input node in this order and transferred through the graph to the output node in a series of moves; each move transfers a token from a node to an adjacent node. Two or more tokens cannot reside on an internal node simultaneously. When the tokens arrive at the output node they will appear in a permutation of their original order. The main result is a description of the possible arrival permutations in terms of regular sets. This description allows the number of arrival permutations of each length to be computed. The theory is then applied to packet-switching networks and has implications for the resequencing problem. It is also applied to some complex data structures and extends previously known results to the case that the data structures are of bounded capacity. A by-product of this investigation is a new proof that permutations which avoid the pattern 321 are in one to one correspondence with those that avoid 312.