Theoretical Computer Science

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:

• First-order logic with reachability for infinite-state systems, by Emanuele D'Osualdo, Roland Meyer, and Georg Zetzsche.
  In Proceedings of LICS 2016.
  PDF | DOI

• The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets, by Georg Zetzsche.
  In Proceedings of RP 2015.
  DOI

• Computing downward closures for stacked counter automata, by Georg Zetzsche.
  In Proceedings of STACS 2015.
  DOI | arXiv

• On Boolean closed full trios and rational Kripke frames, by Markus Lohrey and Georg Zetzsche.
  In Proceedings of STACS 2014.
  DOI

• Semilinearity and Context-Freeness of Languages Accepted by Valence Automata, by P. Buckheister and Georg Zetzsche.
  In Proceedings of MFCS 2013.
  DOI | arXiv

• Silent Transitions in Automata with Storage, by Georg Zetzsche.
  In Proceedings of ICALP 2013.
  DOI | arXiv

• On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids, by Georg Zetzsche.
  In Proceedings of ICALP 2011.
  arXiv | DOI