Computational and logical aspects of infinite monoids

Abstract

The present work contains a treatise of several computational and logical aspects of infinite monoids.

The first chapter is devoted to the word problem for finitely generated monoids. In particular, the relationship between the the computational complexity of the word problem and the syntactical properties of monoid presentations is investigated. The second chapter studies Cayley-graphs of finitely generated monoids under a logical point of view. Cayley-graphs of groups play an important role in combinatorial group theory. We will study first-order and monadic second-order theories of Cayley-graphs for both groups and monoids. The third chapter deals with word equations over monoids. Using the graph product operation, which generalizes both the free and the direct product, we generalize the seminal decidability results of Makanin on free monoids and groups to larger classes of monoids.

Die vorliegende Arbeit enthält eine Betrachtung von Berechenbarkeitsaspekten sowie logischen Eigenschaften unendlicher Monoide.

Das erste Kaptitel beschäftigt sich mit dem Wortproblem für endlich erzeugte Monoide. Insbesondere wird der Zusammenhang zwischen der Berechnungskomplexität des Wortproblems und den syntaktischen Eigenschaften einer Monoidpräsentation untersucht. Im zweiten Kapitel werden Cayley-Graphen von endlich erzeugten Monoiden vom Standpunkt der mathematischen Logik aus untersucht. Cayley-Graphen von Gruppen spielen eine wichtige Rolle in der kombinatorischen Gruppentheorie. Es werden sowohl Theorien erster Stufe als auch monadische Theorien zweiter Stufe von Cayley-Graphen von Gruppen und Monoiden untersucht. Das dritte Kapitel widmet sich Wortgleichungen über Monoiden. Mittels der Graphprodukt-Konstruktion, welche freie sowie direkte Produkte verallgemeinert, werden die bekannten Entscheidbarkeitsresultate von Makanin für freie Monoide und Gruppen auf größere Klassen von Monoiden verallgemeinert.