[MathJax on]

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:

  
gap> hex:=[[2,3],[4],[5],[3,6],[6],[]];
[ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [  ] ]
gap> 

This list represents the following directed graph:

2.1 Specific TPN

In PatternClass there are several functions that define different kinds of specific token passing networks.

2.1-1 Parstacks

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.

  
gap> Parstacks(2,2);
[ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
gap> 

Parstacks(2,2) can be visualised as the following directed graph:

  
gap> Parstacks(4,3);
[ [ 2, 6 ], [ 3, 9 ], [ 2, 4 ], [ 3, 5 ], [ 4 ], [ 7, 9 ], [ 6, 8 ], [ 7 ],
  [  ] ]
gap> 

The token passing network below represents the list that was output by Parstacks(4,3).

2.1-2 Seqstacks

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).

  
gap> Seqstacks(2,2);
[ [ 2 ], [ 3, 4 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
gap> 

Seqstacks(2,2) can be visualised as the following directed graph:

gap> Seqstacks(3,1,4);
[ [ 2 ], [ 3, 5 ], [ 2, 4 ], [ 3 ], [ 4 ], [ 7, 10 ], [ 6, 8 ], [ 7, 9 ], 
  [ 8 ], [  ] ]
gap> 

The token passing network containing a series of stacks of length 3, 1 and 4 looks as follows:

2.1-3 BufferAndStack

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.

  
gap> BufferAndStack(2,2);
[ [ 2, 3 ], [ 4 ], [ 4 ], [ 5, 6 ], [ 4 ], [  ] ]
gap> 

BufferAndStack(2,2) is the following directed graph:

gap> BufferAndStack(4,3);
[ [ 2 .. 5 ], [ 6 ], [ 6 ], [ 6 ], [ 6 ], [ 7, 9 ], [ 6, 8 ], [ 7 ], [  ] ]
gap> 

The token passing network correlating to the list output by BufferAndStack(4,3) is:

generated by GAPDoc2HTML