Developing mathematical formalisms for cellular automata in modelling and simulation

Abstract

Zelluläre Automaten werden in verschiedensten wissenschaftlichen Gebieten als Methode der mathematischen Modellbildung und Simulation angewandt. Für gewöhnlich stellt ein Zellulärer Automat eine mikroskopische Beschreibung oder Abstraktion eines natürlichen Systems dar. Die Werkzeuge für die Herleitung und Validierung eines Modellbildungsansatzes mit Zellulären Automaten sind jedoch oft auf einen konkreten Anwendungsfall ausgelegt. Daher existiert weder ein etablierter mathematischer Formalismus für Zelluläre Automaten als Methode der Modellbildung und Simulation noch allgemeine Methoden für die Analyse und Validierung. Diese Arbeit betrachtet Zelluläre Automaten als einen eigenständigen mathematischen Modellierungsansatz und beinhaltet eine rigorose und systematische Definition von verschiedenen Ausprägungen von Zellulären Automaten. Das Ziel ist es, Methoden und Ansätze für eine generelle Diskussion und einen Vergleich dieses Modellierungsansatzes bereitzustellen. Dabei liegt der Fokus weniger auf der Einführung einer Klassifikation von Zellulären Automaten, sondern auf der Bereitstellung und Vereinfachung von Methoden für Analyse, Validierung und Vergleich. Zusätzlich erleichtert eine systematische Beschreibung von Zellulären Automaten die Vermittlung des gewählten Modellierungsansatzes und legt den Grundstein für weitere und detailliertere Untersuchungen. Die mathematische Beschreibung von Zellulären Automaten in dieser Arbeit basiert auf lokal definierten Aktualisierungsfunktionen, die in iterativer Weise auf einem Graphen oder regelmäßigen Gitter operieren. Ein Schwerpunkt liegt auf der charakteristischen topologischen Struktur, welche Zelluläre Automaten auch von anderen Konzepten wie Agenten-basierten Ansätzen oder allgemeinen Netzwerk Modellen abgrenzt. Weiters wird unter der Bezeichnung Evolutions-Systeme eine Modifikation des Konzepts Zelluläre Automaten mit kontinuierlicher Zeit und Raum betrachtet. Dies liefert schlussendlich eine Verbindung zu stark stetigen Halbgruppen, abstrakten Cauchy Problemen und partiellen Differentialgleichungen. Schließlich stellt ein stochastischer Formalismus diesen Modellierungsansatz als eine spezielle Variante eines Markov Prozesses dar und erlaubt aber gleichzeitig eine effiziente deterministische Methode für die Analyse und Simulation.

Cellular Automata are being applied as a method for mathematical modelling and simulation in a variety of scientific areas. Usually a cellular automaton constitutes a microscopic description or abstraction of a natural system. The tools used for a mathematical derivation and validation of the cellular automaton modelling approach are however often optimised for specific natural systems. As a consequence there exists neither a dedicated mathematical formalism for cellular automata as a method for modelling and simulation nor general methods for model analysis and validation. This thesis regards cellular automata as a distinct mathematical ansatz for modelling and contains a rigorous and systematic definition of various types of cellular automata. The aim is to develop methods and approaches for a general discussion and comparison of this modelling approach. Thereby the focus is less the introduction of a classification of cellular automata than the deduction and simplification of methods for analysis, validation and comparison. Additionally a systematic description of cellular automata can ease the communicability of the chosen modelling approach and provides a basis for further and more specific investigations. The mathematical description of cellular automata in this thesis is based on locally defined update functions that operate in an iterative manner on graphs respectively regular lattices. A strong focus is put on the characteristic topological structure, which also delineates cellular automata from other concepts like agent-based modelling approaches and arbitrary network models. Furthermore a modification of the concept of cellular automata with continuous time and space is introduced under the paradigm of evolution systems, which ultimately yields a connection to strongly continuous semigroups, abstract Cauchy problems and parabolic partial differential equations. A stochastic formalism of cellular automata finally discloses this modelling approach as a very specific variant of Markov processes and allows efficient deterministic methods for analysis and simulation.