chap2.txt

  
  2 Token Passing Networks
  
  A token passing network is a directed graph with a designated input node and
  a  designated  output node. The input node has no incoming edges whereas the
  output  node has no outgoing edges. Also the input node generates a sequence
  of  tokens,  labelled 1, 2, 3, ... . These tokens are passed on to the nodes
  within the graph, where each node, apart from the input and output node, can
  hold  at  most  one  token at any time. The edges do not hold tokens but are
  there  to  pass them on. The following must hold if a token t moves from the
  node x to the node y.
  
  There  is  an edge from x to y; x is the input node, and the tokens 1, 2, 3,
  ...  ,  t-1 have been moved, or x is any other node but not the output node;
  lastly  either y is the output node or y is not the input node and currently
  is not occupied by a token. [3]
  
  Token  passing  networks,  or  TPNs,  are represented in GAP as a list. Each
  entry  of  the  list  is the index of the node within the TPN and contains a
  list  of  the  "destinations", i.e. the end of the edge or arrow where it is
  directed to.
  
  Here is an example how the input of such a TPN looks in GAP:
  
    Example  
    gap> hex:=[[2,3],[4],[5],[3,6],[6],[]];
    [ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [  ] ]
    gap> 
  
  
  From  this  it  is visible that the input node is 1, as it has no other node
  pointing  any  arrows  towards  it,  and  the output node is 6, as it has no
  destinations (hence the empty list).
  
  
  2.1 Specific TPN
  
  In  PatternClass  there are several functions that define different kinds of
  specific token passing networks.
  
  2.1-1 Parstacks
  
  Parstacks( m, n )  function
  Returns:  A  list  that  represents  the  directed  edges of a token passing
            network.
  
  Parstacks  constructs  a token passing network with 2 different sized stacks
  m,n positioned in parallel.
  
    Example  
    gap> Parstacks(2,2);
    [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
    gap> 
  
  
    Example  
    gap> Parstacks(4,3);
    [ [ 2, 6 ], [ 3, 9 ], [ 2, 4 ], [ 3, 5 ], [ 4 ], [ 7, 9 ], [ 6, 8 ], [ 7 ],
      [  ] ]
    gap> 
  
  
  2.1-2 Seqstacks
  
  Seqstacks( n[, m[, o[, p[, ...]]]] )  function
  Returns:  A  list  that  represents  the  directed  edges of a token passing
            network.
  
  The token passing network build by Seqstacks contains a series of stacks (as
  many  as  you  have integers in the arguments list) each of different length
  (each integer in the argument list).
  
    Example  
    gap> Seqstacks(2,2);
    [ [ 2 ], [ 3, 4 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
    gap> 
  
  
    Example  
    gap> Seqstacks(3,1,4);
    [ [ 2 ], [ 3, 5 ], [ 2, 4 ], [ 3 ], [ 4 ], [ 7, 10 ], [ 6, 8 ], [ 7, 9 ], 
      [ 8 ], [  ] ]
    gap> 
  
  
  2.1-3 BufferAndStack
  
  BufferAndStack( m, n )  function
  Returns:  A  list  that  represents  the  directed  edges of a token passing
            network.
  
  BufferAndStack  is a token passing network that consists of a buffer of size
  m which is followed by a single stack of size n.
  
    Example  
    gap> BufferAndStack(2,2);
    [ [ 2, 3 ], [ 4 ], [ 4 ], [ 5, 6 ], [ 4 ], [  ] ]
    gap> 
  
  
    Example  
    gap> BufferAndStack(4,3);
    [ [ 2 .. 5 ], [ 6 ], [ 6 ], [ 6 ], [ 6 ], [ 7, 9 ], [ 6, 8 ], [ 7 ], [  ] ]
    gap>