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.
