Affordable Access

Computing area in group presentations

Authors
  • Riley, Timothy
Type
Preprint
Publication Date
Jul 23, 2016
Submission Date
Jun 28, 2016
Identifiers
arXiv ID: 1606.08833
Source
arXiv
License
Yellow
External links

Abstract

The width of a word $w$ representing an element in a free group $F(a,b)$ was defined by Jiang to be the minimal $N$ such that $w$ freely equals a product of $N$ conjugates of powers of $a$ and $b$. In 1991 Grigorchuk and Kurchanov gave an algorithm computing $N$ and asked whether it could be done in polynomial time. We use dynamic programming answer this affirmatively. The width of $w$ can be reinterpreted as its area with respect to the presentation $\langle a, b \mid a^k, b^k; k \in \mathbb{N} \rangle$ of the trivial group. We also give a polynomial time algorithm finding the areas of words in the group presentation $\langle a, b \mid a, b \rangle$. We explain connections these problems have to computing the minimal number of fixed points in the homotopy class of a continuous self-map of a compact surface, RNA folding, and the design of liquid crystals.

Report this publication

Statistics

Seen <100 times