Habilitation HABIL-2003-01

Bibliograph.
Daten
Lohrey, Markus: Computational and logical aspects of infinite monoids.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Habilitation (2003).
185 Seiten, englisch.
CR-Klassif.F.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
Kurzfassung

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.

Volltext und
andere Links
PDF (2434068 Bytes)
Opus Uni Stuttgart
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum22. Juli 2005
   Publ. Institut   Publ. Informatik