Monoids as Storage Mechanisms

  • Automata theory has given rise to a variety of automata models that consist of a finite-state control and an infinite-state storage mechanism. The aim of this work is to provide insights into how the structure of the storage mechanism influences the expressiveness and the analyzability of the resulting model. To this end, it presents generalizations of results about individual storage mechanisms to larger classes. These generalizations characterize those storage mechanisms for which the given result remains true and for which it fails. In order to speak of classes of storage mechanisms, we need an overarching framework that accommodates each of the concrete storage mechanisms we wish to address. Such a framework is provided by the model of valence automata, in which the storage mechanism is represented by a monoid. Since the monoid serves as a parameter to specifying the storage mechanism, our aim translates into the question: For which monoids does the given (automata-theoretic) result hold? As a first result, we present an algebraic characterization of those monoids over which valence automata accept only regular languages. In addition, it turns out that for each monoid, this is the case if and only if valence grammars, an analogous grammar model, can generate only context-free languages. Furthermore, we are concerned with closure properties: We study which monoids result in a Boolean closed language class. For every language class that is closed under rational transductions (in particular, those induced by valence automata), we show: If the class is Boolean closed and contains any non-regular language, then it already includes the whole arithmetical hierarchy. This work also introduces the class of graph monoids, which are defined by finite graphs. By choosing appropriate graphs, one can realize a number of prominent storage mechanisms, but also combinations and variants thereof. Examples are pushdowns, counters, and Turing tapes. We can therefore relate the structure of the graphs to computational properties of the resulting storage mechanisms. In the case of graph monoids, we study (i) the decidability of the emptiness problem, (ii) which storage mechanisms guarantee semilinear Parikh images, (iii) when silent transitions (i.e. those that read no input) can be avoided, and (iv) which storage mechanisms permit the computation of downward closures.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Author:Georg Zetzsche
Advisor:Roland Meyer
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2016/06/17
Year of first Publication:2016
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2015/06/19
Date of the Publication (Server):2016/06/17
Page Number:X, 189
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
CCS-Classification (computer science):F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.1 Models of Computation (F.4.1) / Automata (e.g., finite, push-down, resource-bounded)
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015