Browsing by Author "Kausch, Jonathan"

Now showing 1 - 2 of 2

Open Access
Normalformenberechnung in Graph-Gruppen und Coxeter-Gruppen
(2011) Kausch, Jonathan
Im Rahmen der Diplomarbeit wurde das Normalformenproblem für partiell kommutative Gruppen in logarithmischem Platz untersucht. Diese Gruppen sind in der Mathematik als Graph-Gruppen oder "rechtwinklige Artingruppen" bekannt und werden u.a. in der kombinatorischen Gruppentheorie untersucht. In der Informatik erscheinen sie als natürliche Erweiterung der Spurmonoide, die von Keller und Mazurkiewicz eingeführt wurden und insbesondere für die Untersuchung von Nebenläufigkeit in der Informatik von Bedeutung sind. Zur Analyse der Normalformenproblemberechnung werden die Graph-Gruppen zunächst in rechtwinklige Coxeter-Gruppen eingebettet. Für beliebige Coxeter-Gruppen kann das Alphabet der längenlexikographischen Normalform in logarithmischem Platz bestimmt werden. Darauf aufbauend kann die längenlexikographische Normalform in rechtwinkligen Coxeter-Gruppen berechnet werden. Für allgemeine Coxeter Gruppen wird in "Combinatorics of Coxeter Groups" (Björner, Brenti) ein Algorithmus vorgestellt, der die Normalform mit linear vielen reellen arithmetischen Operationen und Vergleichen bestimmt. Die Berechnung lässt sich allerdings nicht ausschließlich mit ganzen Zahlen durchführen, sondern es werden komplexe Einheitswurzeln benötigt. In dieser Arbeit wird geklärt, wie viele Bits zur Repräsentation notwendig sind. Außerdem wird ein elementarer Beweis angegeben, der zeigt, dass für Coxeter-Gruppen ein präperfektes Ersetzungssystem existiert. Ein präperfektes Ersetzungssystem ist ein Ersetzungssystem, welches nur längenerhaltende und längenreduzierende Regeln besitzt. Coxeter-Gruppen gehören unter anderem zur Klasse der automatischen Gruppen. Für rechtwinklige Coxeter-Gruppen wird in dieser Arbeit ein Beweis angegeben, der zeigt, dass diese automatisch sind.
Open Access
The parallel complexity of certain algorithmic problems in group theory
(2017) Kausch, Jonathan; Diekert, Volker (Prof. Dr.)
In this thesis, we study the parallel complexity of certain problems in algorithmic group theory. These problems are the word problem, the geodesic and normal form problem and the conjugacy problem. We study these problems for some products of groups, namely direct products, free products and graph products. For all those we consider the problems for a fixed group as well as the uniform versions. Uniform means that the group is part of the input. Among the studied problems, the word problem is the most important one and necessary to solve any of the other problems. For direct products, solving any of the mentioned problems reduces directly to the problems in the base groups of the product. Some of the solutions for the direct product are required for solving the problems of the more complicated products. For free products, we show that the word problem reduces in AC^0 to the word problem of the base groups and the word problem of the free group of rank two. This does hold for the word problem of a fixed free product as well as for the uniform version. For the geodesic and normal form problem of free products, we introduce an equivalence relation. This relation can be decided in AC^0 by using oracle calls to the word problems of the base groups. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. In free products, two cyclically reduced words are conjugate if and only if they are transposed. Direct products and free products are special cases of graph products. A graph product can be written as an amalgamated product of smaller graph products. We first solve the word problem of some restricted amalgamated product. This solution can then be used to solve the word problem of a fixed graph product inductively. We obtain that the word problem of a fixed graph product is AC^0-reducible to the word problem of its base groups and the word problem of the free group of rank two. Unfortunately, this method cannot be used to solve the uniform word problem. We show that the uniform word problem of graph products is NL-hard. For solving it, we introduce an embedding of the graph product into the automorphism group of some (possibly infinite dimensional) vector space. We show that the evaluation of these automorphisms can be realized in GapL and that verifying its result is in CL by using oracle calls to the word problem in the base groups. The uniform word problem of graph products can be reduced to the evaluation of these automorphisms. For the geodesic problem, we introduce another equivalence relation. As for free products, this relation can be decided in AC^0 by using oracle calls to the (uniform) word problem. In graph products the normal form of some word is the length-lexicographic first equivalent word. For solving the normal form problem, first a geodesic and then the lexicographic normal form of this geodesic is computed. We show that for a fixed graph product the computation of the lexicographic normal form is in TC^0 and TC^0-complete for most graph products. We further show that the uniform version is FNL-complete. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. First, we show how to compute cyclically reduced words in AC^0 by using oracle calls to the word problem. Then we show that in graph products two cyclically reduced words are conjugate if and only if they are obtained by a sequence of transpositions. This problem can then be solved by verifying whether the first word is a factor of some power of the second word. For a fixed graph product the factor problem can be decided in AC^0 by using oracle calls to the word problem. For the uniform factor problem we show that it can be decided in NL by using oracle calls to the uniform word problem. Combining all this gives a solution to the (uniform) conjugacy problem of graph products.