Cellular automata and
attributed parallel array grammars

Rudolf FREUND
Technische Universität Wien, Institut für Computersprachen
Resselgasse 3, A-1040 Wien, Austria
email: freund@csafl.tuwien.ac.at
Fritz TAFILL
Technische Universität Wien, Institut für Elektrotechnik und Elektronik,
Arbeitsgruppe für Neuronale Elekronik
Gußhausstraße 25 -- 29, A-1040 Wien, Austria
email: fritz@synapse.iaee.tuwien.ac.at

ABSTRACT. The concept of n-dimensional parallel array grammars (e.g. see [1]) is a useful means for the formal syntactic description of n-dimensional cellular automata ([7]); for the two-dimensional case, a survey of possible applications of array automata like picture recognition is given in [5]. As n-dimensional parallel array grammars are a more general model than n-dimensional cellular automata, they also allow for simpler solutions of complex problems. Attributed parallel array grammars have been shown to be a useful tool for the formal description of the static and dynamic characteristics of neural networks; because of the underlying grid structure, Kohonen's model of self-organizing feature maps (e.g. see [6]) is especially well suited for being represented by n-dimensional parallel array grammars (e.g. see [3], [4]). Using the concept of different levels of scaling like in [2], even hierarchical networks can be modelled by attributed parallel array grammars.

REFERENCES

  1. R. Freund, ``Aspects of n-dimensional Lindenmayer systems'', Developments in Language Theory, Turku, Finland, 1993.
  2. R. Freund, ``Multi-level eco-array grammars'', Artificial Life -- Grammatical Models (Gh. Paun, ed., Black Sea University Press, Bucure\c sti, 1995), pp. 166 -- 174.
  3. R. Freund, F. Tafill, ``Modelling Kohonen networks by attributed parallel array systems'', SPIE'93, Innsbruck, Austria, 1993.
  4. R. Freund, F. Tafill, ``Formal representation of neural networks'', ICANN'94, Sorrento, Italy, 1994.
  5. K. Inoue, I. Takanami, ``A survey of two-dimensional automata theory'', Information Sciences {\bf 55} (1991), pp. 99 -- 121.
  6. H. Ritter, K. Schulten, T. Martinetz, Neuronale Netze (Addison-Wesley, Deutschland, 1990).
  7. S. Wolfram (ed.), Theory and applications of cellular automata (World Scientific Publ., Singapore, 1986).