Master Thesis MSTR-2021-48

BibliographyStober, Florian: The power word problem in graph groups.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 48 (2021).
65 pages, english.
Abstract

This thesis studies the complexity of the power word problem in graph groups. The power word problem is a variant of the word problem, where the input is a power word. A power word is a compact representation of a word. It may contain powers p^x, where p is a finite word and x is a binary encoded integer. A graph group, also known as right-angled Artin group or partially commutative group is a free group augmented with commutation relations. We show that the power word problem in graph groups can be decided in polynomial time, and more precisely it is AC^0-Turing-reducible to the word problem of the free group with two generators F_2. Being a generalization of graph groups, we also look into the power word problem in graph products. The power word problem in a fixed graph product is AC^0-Turing-reducible to the word problem of the free group F_2 and the power word problem of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups C, the uniform power word problem in a graph product is CL-Turing-reducible to the word problem in the free group F_2 and the uniform power word problem in C. Finally, we show that as a consequence of our results on the power word problem the uniform knapsack problem in graph groups is NP-complete.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Diekert, Prof. Volker; Weiß, Dr. Armin
Entry dateNovember 24, 2021
   Publ. Computer Science