<p>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 <span class="SimpleMath">t</span> 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 <span class="SimpleMath">1, ..., t-1</span> 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. <a href="chapBib.html#biBPermGenTPGraph">[ALTnd]</a></p>
<p>The set of permutations resulting from a TPN is closed under the property of containment. A permutation <span class="SimpleMath">a</span> contains a permutation <span class="SimpleMath">b</span> of shorter length if in <span class="SimpleMath">a</span> there is a subsequence that is isomorphic to <span class="SimpleMath">b</span>. This class of permutations can be represented by its anti-chain, which in this context is called the basis. <a href="chapBib.html#biBRegCloSetPerms">[AAR03]</a></p>
<p>To enhance the computability of permutation pattern classes, each permutation can be encoded, using the so called rank encoding. For a permutation <span class="SimpleMath">p_1 ... p_n</span>, it is the sequence <span class="SimpleMath">e_1... e_n</span> where <span class="SimpleMath">e_i</span> is the rank of <span class="SimpleMath">p_i</span> among <span class="SimpleMath">{p_i,p_i+1,...,p_n}</span>. 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. <a href="chapBib.html#biBRegCloSetPerms">[AAR03]</a></p>
<p>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. <a href="chapBib.html#biBPermGenTPGraph">[ALTnd]</a></p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
