# Computing area in group presentations

- Authors
- 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.