Detailansicht
On the word problem for groups
Alexander Bors
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Karl Auinger
DOI
10.25365/thesis.33626
URN
urn:nbn:at:at-ubw:1-30384.40933.424653-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit behandelt das Wortproblem für Gruppen; in drei einleitenden Kapiteln werden der Reihe nach die rekursionstheoretischen (Turing-Maschinen), zahlentheoretischen (Satz von Matiyasevich über Diophantizität und rekursive Aufzählbarkeit) sowie gruppentheoretischen (kombinatorische Gruppentheorie) Grundlagen für die Konstruktion endlicher Gruppenpräsentationen mitunentscheidbarem Wortproblem entwickelt. Im vierten Kapitel wird mit Hilfe dieser Grundlagen nicht nur diese Konstruktion besprochen, sondern auch der Einbettungssatz von Higman bewiesen. Das zur Abrundung dienende fünfte Kapitel bespricht zwei Klassen von Gruppen mit entscheidbarem Wortproblem, nämlich Ein-Relator-Gruppen und hyperbolische Gruppen.
Abstract
(Englisch)
This Master's thesis deals with the word problem for groups; in three preliminary chapters, we successively develop the recursion-theoretic (Turing machines), number-theoretic
(Matiyasevich's Theorem on Diophantineness and recursive enumerability) and group-theoretic (combinatorial group theory) foundations for the construction of finite group presentations with undecidable word problem. In the fourth chapter we discuss not only this construction by means of these foundations, but also prove the Higman Embedding
Theorem. The fifth chapter, which serves to round off the thesis, discusses two classes of groups with decidable word problem, namely one-relator groups and hyperbolic groups.
Schlagwörter
Schlagwörter
(Englisch)
word problem combinatorial group theory group theory groups group presentation recursion theory theoretical computer science computability theory Diophantineness Matiyasevich Turing machine hyperbolic group geometrical group theory 1-relator group logic algebra
Schlagwörter
(Deutsch)
Wortproblem kombinatorische Gruppentheorie Gruppentheorie Gruppen Gruppenpräsentation Rekursionstheorie Theoretische Informatik Berechenbarkeitstheorie Diophantizität Matiyasevich Turing-Maschine hyperbolische Gruppe geometrische Gruppentheorie 1-Relator-Gruppe Logik Algebra
Autor*innen
Alexander Bors
Haupttitel (Englisch)
On the word problem for groups
Paralleltitel (Deutsch)
Über das Wortproblem für Gruppen
Publikationsjahr
2014
Umfangsangabe
II, 79 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Karl Auinger
AC Nummer
AC11817844
Utheses ID
29865
Studienkennzahl
UA | 066 | 821 | |