Institute of

Theoretical Computer Science


Technische Universität Braunschweig

Monoids as Storage Mechanisms

Monoids as Storage Mechanisms

Theoretical Computer Science has established an abundance of automata models that consist of a finite state control and some kind of storage mechanism. Well known examples include pushdown automata, various kinds of counter automata, and Turing machines. Valence automata offer a framework that unifies many of these models: A valence automaton consists of a finite state control and a storage mechanism that is given as a monoid. The storage mechanism is then utilized by including an element of the monoid on each edge, in addition to the input word. Furthermore, a computation is considered valid if composing the monoid elements on the visited edges yields the identity element. Hence, choosing a monoid to use in valence automata consitutes a uniform way of defining a storage mechanism. A variety of such mechanisms, among them the aforementioned examples, can be realized by choosing suitable monoids. This allows us to put results on concrete storage mechanisms in a broader context and ask for which other storage mechanisms they hold. Our project is therefore concerned with generalizing results on automata with storage mechamisms.


Roland Meyer, Emanuele D'Osualdo, and Georg Zetzsche