Monoids as Storage Mechanisms

Abstract

An important theme of automata theory is to study mathematical models of computing
devices with regard to what behavior they can exhibit and what we can
infer about such a device when given a description.
These two types of questions each have their own motivation. The first type
addresses expressiveness. This aspect is important to understand because it explains
what we can compute with limited resources and what systems we can
describe with the respective models. The second type of questions explores the
analyzability of models. This perspective is instrumental when we want to algorithmically
verify properties of systems, which, due to the advent of increasingly
complex and concurrent systems, has become a task of significant importance.
The perspectives of expressiveness and analyzability are deeply intertwined:
They are conflicting qualities insofar as the more expressive a model is, the more
dicult it usually is to analyze. For these reasons, it has become a strong driving
force of today’s research in theoretical computer science to understand how we
can provide models that are expressive enough for a given type of systems and yet
are simple enough to be amenable to analysis. This thesis contributes by studying
the relationship between the computational properties of automata with storage
and the employed storage mechanism.