• Contribute
• What's New
• Submit News

Cellular automata are discrete dynamical systems that can model many complex systems. They have been proved to be successful in serving as an alternative framework for mathematical descriptions of physical systems. With the inspiration from the success of modeling physical systems we would as well like to provide cellular framework for computational systems also. It should be noted that this is preliminary overview of a much generic framework which is still in development and is subjected to change as improvements are adapted - and we gladly welcome constructive criticism, if any. Relevant source code can be found at [1].

What is cellection framework?

Cellection framework is a way of programing the programmable matter. Just the way one solves complex functions with the mechanisms of structured programming methods, cellection framework provides mechanisms for solving the problems using programmable matter methods. What distinguishes the programmable matter is the availability of a massive amount of fine-grained parallelism [2].

In cellular automated worlds it is common for cells to communicate among themselves. Cells that form close neighborhoods undergo the process of communication - affecting each other's state and there by triggering the state changes among themselves. This framework hardly deviates any length from this convention. We use what we call a proposal as the basic unit of communication among the cells. Typically a proposal would be a group of similar objects that share some common property or have agreed upon some common condition. And it is this common condition by which we control the behavior of this framework.

So, what follows here?

If we consider a function as a mapping from a set of inputs to a set of outputs it is obvious that we can classify the whole set of functions into two classes. In the first class we can place all the Functions whose range is confined just to the values of their inputs (e.g. Find Max, Sort) while the second class could be filled with all those whose range is independent of the values of their inputs (e.g. sin, sqrt)

We can understand this classification better by considering the following examples. Consider a function belonging to the first class, say sort. When presented with input {6,2,3} it would produce output {2,3,6} or {6,3,2} depending on its definition. In both cases the output would be a proper subset of the input arguments. On the other hand consider the function sum from the second class of functions. When presented with input arguments {3,5} it would produce output {8} which need not be a subset of the input arguments always.(with few exceptions where one of the arguments is 0. But as a general case we can neglect these special considerations.).

These later type of functions like sum, sin etc… are more common in the theories of mathematics and are mostly used in the applications of mathematical analysis while the former class of functions finds their usage mostly in core computer science algorithms and so in the applications of data analysis. While those later class of functions are enjoying a strong standard support from both the theory and practice of mathematicians, the former class is undergoing daily changes as new techniques evolve and are thus far from a standard frame work. It is with this intention of establishing a common frame work for all the computational functions that we progress with the rest of the paper. And it should be noted that this classification we mentioned before is by no means pure and the functions of one class can be freely moved into another class by appropriately modifying its definition. For example, Find Max instead of directly returning the value of the maximum element, it could return the index of that element and thus could be moved into the later class of functions. So, we assume the reader would use appropriate definition as it suits the context. With this word of caution we welcome (back) the reader to the next section.

This Framework that we are going to examine contains one simple algorithm implemented with cellular automaton. This algorithm would be compatible with any of the functions whose output forms a subset of the input arguments. However, the algorithm does not work directly upon the input members of the original function. Instead, we establish a common relationship among the input members subjected to the requirements of the output and then we submit this relationship as the input to the cellular framework. This way all that the cellular framework sees is a set of Boolean values typically supplied as a table as shown below.

Function()           // The function that we want to
                     // solve in the cellular automated way
Input: {arg1,arg2…argn}
Output: {argi,argj…} // Output values are actual arguments
   where 1<=i,j..<=n           

Cellular Framework:
Input:



  
arg1
arg2
…
argn


  
arg1
-
T



  
arg2
F
-
T


  
…
...



  
argn
T
T
-



Output: {i,j….}    // Output values are indices to argumentsd
    where 1<=i,j..<=n

In the above table true is indicated by T and false by F. The table need not be symmetric. That is, relation(arg_i,arg_j) need not be equal to relation(arg_j,arg_i). And we have placed a `-` for all the values of main diagonal in the table. They typically represent the values of relation(argi,argi). Since those self relations may not be meaningful always, those places can be filled with any value T or F as they would not affect the outcome.

The output of the framework contains indices of the original arguments which when de-indexed gives the desired actual output in terms of the original input arguments.

Thus the steps involved in porting an ordinary function onto this cellular framework are:

1. Identifying the relationship among the input arguments of the original function and there by creating the required Boolean table.
2. Supplying the generated Boolean table to the framework and getting the output by executing it.
3. Decoding the output of the framework such that we get the output of the original function in terms of actual arguments.

1. Any pair of values from the output would satisfy the relationship and
2. All pairs of values from input that satisfy the relationship are present in the output.

The actual method by which the framework operates is as follows. As part of the first step, for the given n-input function first we create a cellular automaton with n-cells and tie each cell with one input. Thus each cell of the automaton represents one (and only one) particular member of the input and so the sequence of states through which the cell may traverse depends not just on the states of the local neighbors but also on the nature of the input member which it has chosen to represent. To facilitate this mapping between the input values and the cellular cells, with each cell we maintain an integer that indexes to a particular member in the input array which it is representing.

Thus having associated the cells with the inputs this way, we now examine how the automaton progresses. In general, the basic mechanism by which any cellular automaton operates is communication. Two or more cells that lie with in a local neighborhood would communicate among themselves and would affect each other resulting in a change of state. Our cellular framework also uses the same mechanism for its operation. Here the basic unit by which two cells communicate is called a proposal. A proposal is nothing but a list of indices that have agreed upon some condition. Typically the condition would be no more than the relation that we have devised as part of the first step, which we have supplied to the framework in the form of a Boolean table.

Considering our one dimensional cellular automata with n cells, all that a cell does at each step is observing the proposal of its immediate right neighbor and copying it onto its own proposal (Cells would be wrapped at the ends). Then the cell would be posed with a choice of either joining the proposal or creating its own version of the proposal from the newly copied proposal. The cell has to take the correct decision based on the contents of the copied proposal and the value of the input argument to which it is indexed. For this it uses the Boolean table that we supplied, as an evaluator function and decides which option it should choose. In case the cell agrees with the newly copied proposal it would join the proposal by appending its index to list of indices that are already present in that proposal and then there ends the matter. However, if the cell does not agree with the newly copied proposal then it would create its own version from the newly copied proposal by discarding all the indices that it does not agree upon. It should be noted that when creating the new version of the proposal from the copied proposal, the copied proposal is not being modified in any way. That is, the copied proposal gets modified only when the cell agrees with it and joins it - otherwise it would be left intact. This new version, the cell would store it in its back proposals queue for later communication. When it observes that there are no more proposals coming from its neighbor it would start publishing them one by one at each time step. This process of generating proposals and publishing them is repeated till there remain no more proposals to generate.

Below we present the algorithm implementing the process that we discussed above.

Class _Proposal
{
  Vector<int>      indices;

Public:
  _Proposal ()     {}
  _Proposal (_Proposal &p)        
  {          
    *this=p;            
  }

  Bool IsOk (int index, bool Table[n][n])
  {
    For (int i=0;i<indices. size();i++)
      If (Table [indices[i]] [index] ==false)
        Return false;
      Return true;
  }

  _Proposal &CreateAValidProposal (int index, bool Table[n] [n])
  {
    _Proposal Prop;

    for(int i=0;i<indices.size();i++)
      if(Table[indices[i]][index])
        Prop.indices.push_back(indices[i]);
      If(Prop.IsIndexPresent(index)==false)
        Prop.indices.push_back(index);
    
    Return Prop;
  }

  Bool operator== (_Proposal &p)
  {
    if (indices.size()!=p.indices.size())
      return false;
    for (int i=0;i<indices.size();i++)
      if (indices[i]!=p.indices[i])
        Return false;
    Return true;
  }

  _Proposal &operator= (_Proposal &p)
  {
    indices.clear();
    For (int i=0; i<p.indices.size ();i++)
      indices.push_back(p.indices[i]);
    
    Return *this;
  }

  Void AppendIndex(int index)
  {
    indices.push_back(index);
  }

  bool IsIndexPresent(int index)
  {
    for(int i=0;i<indices.size();i++)
      if(indices[i]==index)
        return true;
    return false;
  }

  void ConditionalAssign(_Proposal &p)
  {
    if(indices.size()<p.indices.size())
      *this=p;
  }

  bool CompletedATurn(int index)
  {
    if(indices.size()<=0)
      return false;
    return indices[indices.size()-1]==index;
  }
};

Class _Cell
{
  Int        index;
  Int        NextBackProposal;
  Vector%lt;_Proposal>      BackProposals;

Public:
  Bool     valid;
  _Proposal         proposal;
  _Cell ()
  {
    Valid=false;      NextBackProposal=0;
  }

  Bool AgreesWith (_Proposal &p, bool Table[n] [n])
  {
    Return p.IsOk (index, Table);
  }

  Void JoinTheProposal(_Proposal &p)
  {
    if(p.IsIndexPresent(index)==false)
      p.AppendIndex(index);
  }

  Bool PickABackProposal()
  {
    if (NextBackProposal>=BackProposals.size()) 
      Return false;
    Proposal=BackProposals [NextBackProposal++];
    Return true;
  }

  void CreateBackProposal(bool Table[n][n])
  {
    _Proposal backProp;
    backProp=proposal.CreateAValidProposal(index, Table);
    for(int i=0;i<BackProposals.size();i++)
      if(BackProposals[i]==backProp)
        return;
    BackProposals.push_back(backProp);
  }
};

Algorithm ([input] Boolean Table[n] [n])
{
  int         ElectionTimer=0;
  _Cell    cells [MAX] [2];
  _Proposal ElectedProposal;

  cell[n-1][1].valid=true;
  cell[n-1][1].proposal.AppendIndex(n-1);

  for(int tick=0;   ;tick=(tick+1)%2,ElectionTimer++)
  {
    for(int i=0;i<n;i++)
    {
      cell[i][tick].valid=false;
      if(cell[(i+1)%n][(tick+1)%2].valid==false)
      {
        Cell[i][tick].valid=cell[i][tick].PickABackProposal();
        Continue; 
      }
      cell[i][tick].proposal=cell[(i+1)%n][(tick+1)%2].proposal;
      if(cell[i][tick].proposal.CompletedATurn(i))       
      {
        ElectionTimer=0;
        ElectedProposal.ConditionalAssign(cell[i][tick].proposal);
        Cell[i][tick].valid=cell[i][tick].PickABackProposal();
        continue;
      }
      if(true==cell[i][tick].AgreesWith(cell[i][tick].proposal,Table))
        cell[i][tick].JoinTheProposal(cell[i][tick].proposal);
      else
        cell[i][tick].CreateBackProposal(Table);
      cell[i][tick].valid=true;
    }
    if(ElectionTimer>MAX_ELECTION_TIMER)
    break;
  }

  Return ElectedProposal;
}

And for the cellular automata, here we are using a simple one dimensional automaton containing n cells. We have implemented the cell as a class object. Each cell object contains the following members.

• Index - this tells which input member the cell is corresponding to,
• BackProposals – a vector that holds all proposals generated by the cell,
• NextBackProposal – this tells which back proposal should be selected next

• Valid – a Boolean value indicting whether the cell contains a valid proposal or not
• Proposal – the actual proposal that is currently being circulated among the cells for acceptance.

To understand how this framework can actually be applied to real world problems, we explain the procedure by considering an example problem. Let us consider the maximum clique problem. Here the problem is to find the maximum completely connected component from the given graph. We would be supplied with a set of nodes and edges and we are required to output the largest set of nodes that are completely connected. The required output would be a subset of the set of nodes from the input and so we can apply our framework for this problem.

As the first step we need to device the relationship that defines the output. In this case, from the problem statement it is clear that connectivity is one such relation that we can use. We can define this connectivity as the Boolean function that returns true if a pair of nodes is connected and false otherwise. From this we can derive the required n*n Boolean table. In fact for this problem - our derived Boolean table would be nothing but the Adjacency matrix of the graph. This we supply to our actual algorithm which upon some election process returns the elected proposal which contains the required set of indices. We can define the MAX_ELECTION_TIMER to be equal to c*(n+1) where c is any constant >=2.

The process of election can be understood by considering some hypothetical data. Consider the graph shown in the adjacent figure. The execution sequence could be visualized as follows:

Table 1: At time t=0

BackProposals				Cell Index	Proposal
				1
				2
				3
				4
				5	5

Table 2: At time t=1

BackProposals				Cell Index	Proposal
				1
				2
				3
				4	5,4
				5

Table 3: At time t=2

BackProposals				Cell Index	Proposal
				1
				2
				3	5,4,3
				4
				5

Table 4: At time t=3

BackProposals				Cell Index	Proposal
				1
			5,4,2	2	5,4,3
				3
				4
				5

Table 5: At time t=4

BackProposals				Cell Index	Proposal
			5,3,1	1	5,4,3
			5,4,2	2	5,4,2
				3
				4
				5

Table 6: At time t=5

BackProposals				Cell Index	Proposal
			5,3,1	1	5,4,2
			5,4,2	2
				3
				4
				5	5,4,3

Table 7: At time t=6

BackProposals				Cell Index	Proposal
			5,3,1	1	5,3,1
			5,4,2	2
				3
				4	5,4,3
				5	5,4,2

Table 8: At time t=7, Elected Proposal = {5,4,3}

BackProposals				Cell Index	Proposal
			5,3,1	1
			5,4,2	2
				3	5,4,3
				4	5,4,2
				5	5,3,1

Table 9: At time t=8, Elected Proposal = {5,4,3}

BackProposals				Cell Index	Proposal
			5,3,1	1
			5,4,2	2
				3	5,4,2
				4	5,3,1
				5	-

Table 10: At time t=9, Elected Proposal = {5,4,3}

BackProposals				Cell Index	Proposal
			5,3,1	1
			5,4,2	2	5,4,2
				3	5,3,1
				4
				5	-

This is an example where the order of elements is not cared for. However for some problems order in which elements are output is also important. One such problem is sorting. The framework can take care of such problems also. However, proper care should be taken while designing the Boolean relationship table for the input arguments.

For example, if we wanted to port the problem of sorting onto our cellular framework then as the first step we need to devise a Boolean relationship among the input numbers such that all the output numbers satisfy the relationship. Consider the problem of sorting a set of n number in ascending order. The output numbers should satisfy the property that output[i]<=output[j] when i<j. Thus we can use this <= as the relationship among the input arguments and can devise the Boolean table accordingly.

However, as expressed earlier, the success of this framework completely depends on the wise selection of the Boolean relationship and the construction of the appropriate Boolean table. And devising that relationship is more an art just like creating appropriate classes for an object oriented problem. However, once we are guaranteed that our devised relationship is proper then we can as well be guaranteed that the output would be correct. This we can prove easily by considering the fact that no duplicate proposals are processed and no processed proposal gets reduced in its length (i.e. the number of indices). Thus the algorithm generates only a finite number of proposals and the only modification that ever could be done to a proposal is adding a new index. Hence the two following observations can be made.

1. If a cell does not agree with a proposal it would rather not join the proposal and so no two indices in the proposal would ever contradict with each other. This satisfies our first condition from the requirements of the output that any pair of values from the output should satisfy the Boolean relationship.
2. And the more the cells agree upon a proposal the more the longer it would become and so the more certain that it would finally be elected as the output, which satisfies our second condition that all the pairs from input that satisfy the relation should be present in the output. Hence we can be assured of the correctness of the output subjected to the validity of the relation that we have devised.

But Why Cellection Framework?

1. The first and foremost reason is that this would allow a common framework for all computational problems to operate upon and so maintenance is easy.
2. We do not need to solve the new problems entirely ourselves. We can just find a way of porting them onto this framework and then can see them being solved automatically.
3. We could, in course of time, establish a relationship among the problems themselves by studying the relations among the arguments that we are establishing as part of this process. After all, two instances of the same function calls could differ only in its arguments. With this we conclude this article by inviting the problem solvers to use this framework in solving their computational problems. We hope we could soon realize many not yet discovered inherent potentials of cellular automata and may find ways of utilizing them and there by providing more advanced mechanisms of computations.

Hmmm...Anything else?

1. Relevant source code for this frame work can be found at: The Page of Links.

2. Tommaso Toffoli, Programmable Matter Methods, Future Generation Computer Systems, June 98.

3. Norman Margolus, Physics-like models of computation, Physica D: Nonlinear Phenomena, Volume 10, Issues 1-2, January 1984.

4. Gérard Y. Vichniac, Simulating physics with cellular automata, Physica D: Nonlinear Phenomena, Volume 10, Issues 1-2, January 1984.

5. Tommaso Toffoli, Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics, Physica D: Nonlinear Phenomena, Volume 10, Issues 1-2, January 1984.

6. Christopher G. Langton, Self-reproduction in cellular automata, Physica D: Nonlinear Phenomena, Volume 10, Issues 1-2, January 1984.