Affordable Access

Computing area in group presentations

Authors
Type
Preprint
Publication Date
Submission Date
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.

Statistics

Seen <100 times