chap1.txt

  
  1 Introduction
  
  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]