Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

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.

Team:

Roland Meyer, Emanuele D'Osualdo, and Georg Zetzsche

Publications: