Titel: KIK-Vortrag "Monoids as Storage Mechanisms" - Dr. ..
Startdatum: 04 Mai
Startzeit: 16:00
Stoppzeit: 17:00Uhr
Veranstalter: FG Intelligente Eingebettete Systeme
Ort: Wilhelmshöher Allee 71-73, Hörsaal 0315

Dr. Georg Zetzsche
(Gewinner des EATCS Distinguished Dissertation Award 2016)
(ENS Paris-Saclay)


"Monoids as Storage Mechanisms"

The investigation of models extending finite automata by some storage mechanism is a central theme in theoretical computer science. Choosing an appropriate storage mechanism can yield a model that is expressive enough to capture a given behavioral aspect while admitting desired means of analysis.

It is therefore a central concern to understand which storage mechanisms have which properties regarding expressiveness and (algorithmic) analysis. This talk presents a line of research that aims for general insights in this direction. In other words:

How does the structure of the storage mechanism influence expressiveness and analysis of the resulting model?

In order to study this question, one needs a model in which the storage mechanism appears as a parameter. Such a model is available in valence automata, where the storage mechanism is given by a (typically infinite) monoid. Choosing a suitable monoid then yields models such as Turing machines, pushdown automata, vector addition systems, or combinations thereof.

This talk surveys a selection of results that characterize storage mechanisms with certain desirable properties, such as decidability of reachability, semilinearity of Parikh images, and decidability of logics.