Token passing networks (TPNs) are directed graphs with nodes that can hold at most one token. Also each graph has a designated input node, which generates an ordered sequence of numbered tokens and a designated output node that collects the tokens in the order they arrive at it. The input node has no incoming edges, whereas the output node has no outgoing edges. A token t travels through the graph, from node to node, if there is an edge connecting the nodes, if the node the token is moving from is either the input node and the tokens 1, ..., t-1 have been released or the node is not the output node, and lastly if the destination node contains no token or it is the output node. [3]
The set of permutations resulting from a TPN is closed under the property of containment. A permutation a contains a permutation b of shorter length if in a there is a subsequence that is isomorphic to b. This class of permutations can be represented by its anti-chain, which in this context is called the basis. [2]
To enhance the computability of permutation pattern classes, each permutation can be encoded, using the so called rank encoding. For a permutation p_1 ... p_n, it is the sequence e_1... e_n where e_i is the rank of p_i among {p_i,p_i+1,...,p_n}. It can be shown that the sets of encoded permutations of the class and the basis, both are a rational languages. Rational languages can be represented by automata. [2]
There is another approach to get from TPNs to their corresponding automata. Namely building equivalence classes from TPNs using the different dispositions of tokens within them. These equivalence classes of dispositions and the rank encoding of the permutations allow to build the same rational language as from the process above. [3]
generated by GAPDoc2HTML