Postdoctoral Qualification HABIL-2003-01

BibliographyLohrey, Markus: Computational and logical aspects of infinite monoids.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Postdoctoral Qualification (2003).
185 pages, english.
CR-SchemaF.4.2 (Grammars and Other Rewriting Systems)
F.1.1 (Models of Computation)
F.1.3 (Complexity Measures and Classes)
F.4.1 (Mathematical Logic)
KeywordsMathematical Logic; Word problems; Groups; Monoids; Decidability; Complexity; Cayley-graphs
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 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-graphsfor 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 Makaninon free monoids and groups to larger classes of monoids.

Full text and
other links
PDF (2434068 Bytes)
Opus Uni Stuttgart
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateJuly 22, 2005
   Publ. Computer Science